10.23 闲话

10.23 闲话 图论复习

还有2天就复赛了，现在暂时不知道做啥题了，写一下这两天复习的图论知识。
1.存图方式

(1.) 邻接矩阵

没什么好说的，最简单的存图方式，一眼就会。
定义矩阵数组 \(a[n][n](n为点的数量数)\) ，\(a[v]=w\) 代表 \(u,v\) 之间存在一条权值为 \(w\) 的路径。
由于采用二维数组存图，导致其在稠密图中效率低下，会有很多空间被浪费掉，限制了其发挥。
(2.) \(vector\)

动态数组存图，比较好写也比较常用的一种方式，定义的话为 \(vectora[n](n为点的数量)\) 对于 \(a=v\) 来说，其代表点 \(u\) 的第 \(i\) 条边的终点是 \(v\) ，若需存储其权值，则需要改变其数据类型，使用结构体类型。
存储权值的方式以及遍历点 \(i\) 的所有出度的方式。

1. struct node{
2.         int id,w;
3. };
4. vector<node>a[maxn];
5. //向点u压入一条权值为w的通往v的出度
6. a[u].push((node){v,w});
7. for(int j=0;j

复制代码

比起邻接矩阵存图，其省去了大量的冗余空间存储不存在的边。故其在稀疏图的表现明显优于邻接矩阵。
(3.)链式前向星

学的不太好，可能讲起来会比较抽象。
建立结构体数组 \(e[m](m为边的数量)\) 结构体的变量为 \(to(边的终点),next(其同起点的一个兄弟)，w(边的权值)\) ，与一个 \(head\) 数组， \(head\) 表示 \(i\) 点的最近一条连边。
存储方式及遍历方法：

1. struct edge{
2.     int to,next,w;
3. }e[m];
4. int head[n];
5. void add_edge(int u,int v,int w){  //添加一条由u通向v的权值为w的边
6.     tot++;               //tot为当前边的编号
7.         e[tot].to=v;         //边的终点
8.     e[tot].next=head[u]; //更新其兄弟
9.     e[tot].w=w;
10.     head[u]=tot;         //记录u点的最近一条出度
11. }
12. //遍历点x的所有出度
13. for(int i=head[x];i;i=e[i].next){   //最早的点的next值为0
14.    
15. }

复制代码

较起前两种，链式前向星由于不用存储起点，只存储边，不由点决定，决定其空间利用率极高，是最省空间的存图方式。
2.拓扑排序

首先阐述其的定义，在一张 \(DAG(有向无环图)\) 中，若 \(i,j\) 存在一条由 \(i\) 指向 \(j\) 的边，则称 \(j\) 依赖于 \(i\) ，则拓扑排序的目的就是使排序后排在前面的点不依赖于后面的点。
可能有点抽象，形象点来说，就是在一张由有向无环图中，输出入度为零的点，同时将其所连的点的入度减一，重复此过程，直到所有的点都已被输出。这也点出了我们的解决思路，队列存储入度为零的点，当队列非空时，每次取出队首，遍历其所有出度，将其能到达的点的入度减一，若减为零，则将其加入队列，否则继续遍历。
[code]int idx[maxn];                          //入度数组vectore[n];queuequ;for(int i=1;i