基于DFS的拓扑排序

摘录一段维基百科上的伪码：

L ← Empty list that will contain the sorted nodes
S ← Set of all nodes with no outgoing edges
for each node n in S do
    visit(n)
function visit(node n)
    if n has not been visited yet then
        mark n as visited
        for each node m with an edgefrom m to ndo
            visit(m)
        add n to L

DFS的实现更加简单直观，使用递归实现。利用DFS实现拓扑排序，实际上只需要添加一行代码，即上面伪码中的最后一行：add n to L。

需要注意的是，将顶点添加到结果List中的时机是在visit方法即将退出之时。

这个算法的实现非常简单，但是要理解的话就相对复杂一点。

关键在于为什么在visit方法的最后将该顶点添加到一个集合中，就能保证这个集合就是拓扑排序的结果呢？

因为添加顶点到集合中的时机是在dfs方法即将退出之时，而dfs方法本身是个递归方法，只要当前顶点还存在边指向其它任何顶点，它就会递归调用dfs方法，而不会退出。因此，退出dfs方法，意味着当前顶点没有指向其它顶点的边了，即当前顶点是一条路径上的最后一个顶点。

下面简单证明一下它的正确性：

考虑任意的边v->w，当调用dfs(v)的时候，有如下三种情况：

dfs(w)还没有被调用，即w还没有被mark，此时会调用dfs(w)，然后当dfs(w)返回之后，dfs(v)才会返回

dfs(w)已经被调用并返回了，即w已经被mark

~~dfs(w)已经被调用但是在此时调用dfs(v)的时候还未返回~~

需要注意的是，以上第三种情况在拓扑排序的场景下是不可能发生的，因为如果情况3是合法的话，就表示存在一条由w到v的路径。而现在我们的前提条件是由v到w有一条边，这就导致我们的图中存在环路，从而该图就不是一个有向无环图(DAG)，而我们已经知道，非有向无环图是不能被拓扑排序的。

那么考虑前两种情况，无论是情况1还是情况2，w都会先于v被添加到结果列表中。所以边v->w总是由结果集中后出现的顶点指向先出现的顶点。为了让结果更自然一些，可以使用栈来作为存储最终结果的数据结构，从而能够保证边v->w总是由结果集中先出现的顶点指向后出现的顶点。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<cmath>
 6 #include<queue>
 7 #include<stack>
 8 #include<map>
 9 #include<set>
10 #include<sstream>
11 #include<functional>
12 using namespace std;
13 typedef long long ll;
14 const int maxn = 1000 + 10;
15 const int INF = 1e9 + 7;
16 int T, n, m, cases;
17 vector<int>Map[maxn];
18 int c[maxn];//标记数组c[i] = 0 表示还未访问过点i， c[i] = 1表示已经访问过点i，并且还递归访问过它的所有子孙，c[i] = -1表示正在访问中，尚未返回
19 int topo[maxn], t;
20 bool dfs(int u)//从u出发
21 {
22     c[u] = -1;//访问标志
23     for(int i = 0; i < Map[u].size(); i++)
24     {
25         int v = Map[u][i];
26         if(c[v] < 0)return false;//如果子孙比父亲先访问，说明存在有向环，失败退出
27         else if(!c[v] && !dfs(v))return false;//如果子孙未被访问，访问子孙返回假，说明也是失败
28     }
29     c[u] = 1;
30     topo[--t] = u;//在递归结束才加入topo排序中，这是由于在最深层次递归中，已经访问到了尽头，此时才是拓扑排序中的最后一个元素
31     return true;
32 }
33 bool toposort()
34 {
35     t = n;
36     memset(c, 0, sizeof(c));
37     for(int u = 1; u <= n; u++)if(!c[u])
38         if(!dfs(u))return false;
39     return true;
40 }
41 int main()
42 {
43     while(cin >> n >> m)
44     {
45         if(!n && !m)break;
46         int u, v;
47         for(int i = 0;  i <= n; i++)Map[i].clear();
48         for(int i = 0; i < m; i++)
49         {
50             cin >> u >> v;
51             Map[u].push_back(v);
52         }
53         if(toposort())
54         {
55             cout<<"Great! There is not cycle."<<endl;
56             for(int i = 0; i < n; i++)cout<<topo[i]<<" ";
57             cout<<endl;
58         }
59         else cout<<"Network has a cycle!"<<endl;
60     }
61     return 0;
62 }