拓扑排序的实现（基于邻接表实现）_基于邻接表完成拓补排序

问题

给出一个DAG，按事情的先后顺序给事件排序。

思路

利用队列，将所有入度为0的结点加入队列。队首元素出队，去除从该元素引出的边，相应的结点入度减一，如果减完后，结点入度为0，则加入队列。

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1000;

vector<int> G[maxn];
int n,m,inDegree[maxn];

bool topologicalSort(){
    int num = 0;
    queue<int> q;
    for (int i = 0; i < n; ++i) {
        if(inDegree[i] == 0)
            q.push(i);
    }
    while (!q.empty()){
        int u = q.front();
        q.pop();
        for (int i = 0; i < G[u].size(); ++i) {
            int v = G[u][i];
            inDegree[v] = inDegree[v]-1;
            if(inDegree[v] == 0)
                q.push(v);
        }
        G[u].clear();
        num++;
    }
    if(num == n) return true;
    else return false;
}
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

总结

拓扑排序可以用于判断有向图是否有环。