拓扑排序是对有向无环图(DAG)进行排序，从而找到一个序列。该序列满足对于任意一对不同的顶点u,v∈V，若G中存在一条从u->v的边，则在此序列中u在v前面。
拓扑排序也可以用来判断一个有向图是否存在环。
有两种算法可以求得该序列：
1.Kahn算法。
其实就是不断的寻找有向图中没有前驱(入度为0)的顶点，将之输出。然后从有向图中删除所有以此顶点为尾的弧。重复操作，直至图空，或者找不到没有前驱的顶点为止。
该算法还可以判断有向图是否存在环(存在环的有向图肯定没有拓扑序列)，通过一个count记录找出的顶点个数，如果少于N则说明存在环使剩余的顶点的入度不为0。（degree数组记录每个点的入度数）
模板代码1：
#include <bits/stdc++.h> using namespace std; const int maxn = 505; struct node { int v, next; }edge[maxn*maxn]; int degree[maxn], head[maxn]; queue<int> q; list<int> ans; int n, m, no; inline void init() { no = 0; while(!q.empty()) q.pop(); memset(degree, 0, sizeof degree); memset(head, -1, sizeof head); } inline void add(int u, int v) { edge[no].v = v; edge[no].next = head[u]; head[u] = no++; } int Kahn() { int count = 0; while(!q.empty()) { int tp = q.front(); q.pop(); ++count; ans.push_back(tp); //加入链表中，加入数组或者vector或者queue都无所谓 int k = head[tp]; while(k != -1) { --degree[edge[k].v]; if(!degree[edge[k].v]) q.push(edge[k].v); k = edge[k].next; } } if(count == n) return 1; return 0; } int main() { int u, v; scanf("%d %d", &n, &m); init(); for(int i = 1; i <= m; ++i) { scanf("%d %d", &u, &v); add(u, v); ++degree[v]; } for(int i = 1; i <= n; ++i) { if(!degree[i]) q.push(i); } Kahn(); list<int>::iterator it; for(it = ans.begin(); it != ans.end(); ++it) { cout << *it << " "; } cout << endl; return 0; }
2.基于DFS的求解方法。
算法导论对于该种方法讲述的比较详细，由于它用的单链表存边，下面我只贴一份自己的模板代码。
思想基于：DFS时候，遇到u->v边，通过在DFS函数快退出时将结点加入到List中实现v在序列的位置始终在u的前
面。反向序列即为所求的拓扑序列。（这篇博文有整理算法导论的拓扑排序部分）
模板代码2：
#include <bits/stdc++.h> using namespace std; const int maxn = 505; struct node { int v, next; }edge[maxn*maxn]; int head[maxn], vis[maxn]; list<int> ans; int n, m, no; inline void init() { no = 0; memset(head, -1, sizeof head); memset(vis, 0, sizeof vis); } inline void add(int u, int v) { edge[no].v = v; edge[no].next = head[u]; head[u] = no++; } void DFS(int cur) { vis[cur] = 1; int k = head[cur]; while(k != -1) { if(!vis[edge[k].v]) DFS(edge[k].v); k = edge[k].next; } ans.push_back(cur); } int main() { int u, v; scanf("%d %d", &n, &m); init(); for(int i = 1; i <= m; ++i) { scanf("%d %d", &u, &v); add(u, v); } for(int i = 1; i <= n; ++i) { if(!vis[i]) DFS(i); } list<int>::reverse_iterator it; for(it = ans.rbegin(); it != ans.rend(); ++it) { cout << *it << " "; } cout << endl; return 0; } 继续加油~
