10.23 闲话
10.23 闲话 图论复习还有2天就复赛了，现在暂时不知道做啥题了，写一下这两天复习的图论知识。
1.存图方式
(1.) 邻接矩阵
没什么好说的，最简单的存图方式，一眼就会。
定义矩阵数组 \(a(n为点的数量数)\) ，\(a=w\) 代表 \(u,v\) 之间存在一条权值为 \(w\) 的路径。
由于采用二维数组存图，导致其在稠密图中效率低下，会有很多空间被浪费掉，限制了其发挥。
(2.) \(vector\)
动态数组存图，比较好写也比较常用的一种方式，定义的话为 \(vectora(n为点的数量)\) 对于 \(a=v\) 来说，其代表点 \(u\) 的第 \(i\) 条边的终点是 \(v\) ，若需存储其权值，则需要改变其数据类型，使用结构体类型。
存储权值的方式以及遍历点 \(i\) 的所有出度的方式。
struct node{
int id,w;
};
vector<node>a;
//向点u压入一条权值为w的通往v的出度
a.push((node){v,w});
for(int j=0;j比起邻接矩阵存图，其省去了大量的冗余空间存储不存在的边。故其在稀疏图的表现明显优于邻接矩阵。
(3.)链式前向星
学的不太好，可能讲起来会比较抽象。
建立结构体数组 \(e(m为边的数量)\) 结构体的变量为 \(to(边的终点),next(其同起点的一个兄弟)，w(边的权值)\) ，与一个 \(head\) 数组， \(head\) 表示 \(i\) 点的最近一条连边。
存储方式及遍历方法：
struct edge{
int to,next,w;
}e;
int head;
void add_edge(int u,int v,int w){//添加一条由u通向v的权值为w的边
tot++; //tot为当前边的编号
e.to=v; //边的终点
e.next=head; //更新其兄弟
e.w=w;
head=tot; //记录u点的最近一条出度
}
//遍历点x的所有出度
for(int i=head;i;i=e.next){ //最早的点的next值为0
}较起前两种，链式前向星由于不用存储起点，只存储边，不由点决定，决定其空间利用率极高，是最省空间的存图方式。
2.拓扑排序
首先阐述其的定义，在一张 \(DAG(有向无环图)\) 中，若 \(i,j\) 存在一条由 \(i\) 指向 \(j\) 的边，则称 \(j\) 依赖于 \(i\) ，则拓扑排序的目的就是使排序后排在前面的点不依赖于后面的点。
可能有点抽象，形象点来说，就是在一张由有向无环图中，输出入度为零的点，同时将其所连的点的入度减一，重复此过程，直到所有的点都已被输出。这也点出了我们的解决思路，队列存储入度为零的点，当队列非空时，每次取出队首，遍历其所有出度，将其能到达的点的入度减一，若减为零，则将其加入队列，否则继续遍历。
int idx; //入度数组vectore;queuequ;for(int i=1;i
页:
[1]