多日以来被图论狠狠的羞辱，下定决心学习图论基础链式前向星和拓扑排序
图的存储方式
邻接表
规模大的稀疏图可用邻接表，存储复杂度为\(O(n + m)\)。n表示点的数量，m表示边的数量。
struct edge{
int from, to, w;
edge(int a, int b, int c) {
from = a; to = b; w = c;
}
}
vector<edge>e[N];
for (int i = 1; i <= n; i++)
e[i].clear();//初始化
//存边
e[a].push_back(edge(a, b, c));
//遍历所有邻居
for (int i = 0; i < e[u].size(); i++) {
//for (int v:e[u])
int v = e[u][i].to, w = e[u][i].w;
}
链式前向星
实际在存储邻接边的过程也是先定位某个点的第一条边，再定位第二条边，由此可以设计没有任何空间浪费、变成非常简单的存图方法。
- \(head[]\)作为静态数组，\(head[u]\)指向\(u\)的一个邻居的存储位置。
- \(struct\ edge\)是结构静态数组，\(edge[i].to\)存储邻居节点编号，\(edge[i].next\)指向下一个邻居节点的存储位置\(j\)，对应的下一个邻居存储在\(edge[j]\)中。
- \(cnt\)代表当前的存储位置，或者说新加入的边会存储在\(edge[cnt]\)。
- 获取\(u\)对应新的边，插入到\(head[u]\)的方式为头插法，将其插入到\(head[u]\)对应的第一个位置。
也可以将edge结构体转化成为两个不同的数组\(e[]\)和\(ne[]\)进行实现。
int head[N],cnt;
struct {
int from, to, next;//起点，终点，下一个邻居
int w;//边权
}edge[M];//数组存储边
void init(){
for (int i = 0; i < N; ++i) head[i] = -1;//点初始化
//由于头插法，初始化点的-1一定会被传递到链末端，所以可以不初始化边
for (int i = 0; i < M; ++i) edge[i].next = -1;//边初始化
cnt = 0;
}
void addedge(int u, int v, int w) {
edge[cnt].from = u;
edge[cnt].to = v;
edge[cnt].w = w;
//头插法插入节点
edge[cnt].next = head[u];//下一个邻居的存储位置
head[u] = cnt++;//cnt代表新边存储位置
//附上数组对应的实现方式
//e[cnt] = v;
//ne[cnt] = head[u];
//w[cnt] = w;
//head[u] = cnt++;
}
//~1仅对-1有效，0已经是有效空间
for (int i = head[2]; ~i; i = edge[i].next)//遍历节点2的所有邻居，i != -1
printf(" %d - %d", edge[i].from, edge[i].to);
拓扑排序
终于到
不知道为什么总能发挥作用的拓扑排序部分
拓扑排序的概念
一个图能够进行拓扑排序的充要条件是它是一个有向无环图(DAG)。
如果图中有环，可以使用拓扑排序找到环。若本身为无向图，可以通过拓扑排序的BFS，依次将度（即包含出度和入度）为1的点和对应的边去除，若邻居度变为1则入队，直到队列为空。剩余度大于1的点为环上的点。这种无向图找环的方式仅适用于只有一个环的基环树。
基于BFS的拓扑排序
- 无前驱的顶点优先
- 将所有入度为0的点放入队列。
- 弹出队首，邻居点入度-1，入度为0的邻居节点入队。
- 继续直到队列为空。
队列已空但还有点未入队，说明图不是DAG，没有进入队列的就是环上的点
- 无后继的顶点优先：即出度为0的点开始
BFS拓扑排序的时间复杂度
- 查找入度为0的点，检查每条边复杂度\(O(m)\)
- 队列操作中，每个点进出队列一次，并且检查对应所有邻居\(O(n + m)\)
基于DFS的拓扑排序
DFS深度搜索是沿着一条路径一直搜索到底部，然后逐层回退，正好体现点与点的先后关系，天然符合拓扑排序。
对于有向无环图，如果只有一个点u是0入度，直接进行DFS递归返回的顺序就是逆序的拓扑排序。
需要处理的细节
- 如何找到入度为0的点开始DFS？如何处理多个入度为0的点？
设置一个虚拟的点，单向连接到所有其它的点。实际编程直接遍历每个点轮流执行一遍DFS即可。 - 如果图不是DAG，说明是有环图，递归时，会出现**回退边*
输出拓扑排序
使用回溯输出所有的拓扑排序
使用topo[]记录排序，vis标记是否访问，indegree记录入度
void dfs(int z, int cnt) {
int i;
topo[cnt] = z;
if (cnt == n - 1) {
for (int i = ; i < n; i++) printf("%c", topo[i] + 'a');
printf("\n");
return ;
}
vis[z] = 1;
for (int i = 0; i < n; i++) {
if (!vis[a[i]] && dir[z][a[i]])
indegree[a[i]]--;//所有下属入度减1
}
//使用回溯的方式遍历所有可能的拓扑排序
for (int i = 0; i < n; i++)
if (!indegree[a[i]] && !vis[a[i]])//入读为0继续取
dfs(a[i], cnt + 1);
for (int i = 0; i < n; i++) {
if (!vis[a[i]] && dir[z][a[i]])
indegree[a[i]]++;
}
vis[z] = 0;
}
//从所有入度为0的点开始
for (int i = 0; i < n; i++) {
if (!indegree[a[i]])
dfs(a[i], 0);
printf("\n");
}