拓扑排序

一、介绍

适用于有向无环图(DAG)，节点 => 任务，边 => 依赖关系，箭头从前置任务指向后置任务，目标是将任务按依赖关系排序

结果不唯一

二、实现方式

（1）Kahn 算法 (BFS)

流程

image-20260404153059770

先让入度为0的节点入队，一开始队列里是A和B，把A取出放入排序结果，将其指向的C的入度减1，再取出B，放入排序结果，并将其指向的C和D的入度减一。此时C和D的入度为0，继续将其加入队列。最终可以得出ABCDEF。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
void solve(){
    int n;
    cin >> n;
    vector<vector<int> > g(n+1);
    vector<int> deg(n+1,0);
    queue<int> q;
	for(int i = 1;i <= n;++i){
		int v;
		while(cin >> v && v){
			deg[v]++;
			g[i].push_back(v);
		} 
	}
    
    for(int i = 1;i <= n;++i){
        if(deg[i] == 0){
            q.push(i);
        }
    }
	while(!q.empty()){
		auto v = q.front();
		q.pop();
		cout << v << " ";
		for(auto u : g[v]){
			deg[u]--;
			if(deg[u] == 0){
				q.push(u);
			}
		}
	}
    return;
}

（2）DFS

有这种方式，但是编者不用也不会。

相关文章

[[5-2-3-Dijkstra]] [[5-3-2-MST]]