拓扑排序学习笔记

WiuehPlus的博客 / 2023-08-15 / 原文

模板题

分析题目

求一个图的拓扑序。需要用到拓扑排序。

拓扑排序

将一张图中的顶点以线性方式进行排序，使得对于任何的顶点 \(u\) 到 \(v\) 的有向边 \((u,v)\), 都可以有 \(u\) 在 \(v\) 的前面。
并且拓扑排序只能在有向无环图（DAG）中完成。

做法：每次找到入度为 \(0\) 的顶点，将这个顶点列入拓扑序中，并将这个顶点及其相连的边删去。
删去之后再找到入度为 \(0\) 的顶点，重复以上操作，直到所有点都被删去。至此拓扑排序完成。

代码

BFS

考虑建图时开一个数组 \(ind\)，\(ind_i\) 表示编号为 \(i\) 的顶点的入度数量。
然后进行拓扑排序：
定义一个队列 \(q\) 为上一次操作中被删去的入度为 \(0\) 的点。
首先遍历 \(ind\) 数组，找出入度为 \(0\) 的顶点，存入队列 \(q\)，并纳入拓扑序。
每次取出 \(q\) 的队首，遍历它所有的出边，将与它相连的所有顶点的 \(ind\) 减去 \(1\)（相当于删去与它相连的边的操作）。判断如果 \(ind_i=0\)，那么将这个点也放入队列中等待操作，并也将这个点纳入拓扑序。
重复操作，直到队列为空（整个过程相当于BFS）。

代码实现：

#include <bits/stdc++.h>
#define int long long
const int N = 1005;
using namespace std;
inline int read(){
    int r = 0,w = 1;
    char c = getchar();
    while (c < '0' || c > '9'){
        if (c == '-'){
            w = -1;
        }
        c = getchar();
    }
    while (c >= '0' && c <= '9'){
        r = (r << 3) + (r << 1) + (c ^ 48);
        c = getchar();
    }
    return r * w;
}
struct edge{
	int nxt,to;
}e[N];
int cnt = 0,head[N];
void edge_add(int x,int y){
	cnt++;
	e[cnt].nxt = head[x];
	head[x] = cnt;
	e[cnt].to = y;
}
int n,ind[N];
void topo(){
	queue<int>q;
	for (int i = 1;i <= n;i++){
		if (!ind[i]){
			q.push(i);
			printf("%lld ",i);
		}
	}
	while (!q.empty()){
		int tmp = q.front();
		q.pop();
		for (int i = head[tmp];i;i = e[i].nxt){
			int v = e[i].to;
			ind[v]--;
			if (!ind[v]){
				q.push(v);
				printf("%lld ",v);
			}
		} 
	}
}
signed main(){
	n = read();
    for (int i = 1;i <= n;i++){
    	int x = read();
    	while (x){
    		edge_add(i,x);
    		ind[x]++;
    		x = read();
		}
	}
	topo();
    return 0;
}