首页 > 代码库 > 图基本算法 拓扑排序（基于dfs)
图基本算法 拓扑排序（基于dfs)
拓扑排序，是对有向无回路图进行排序，以期找到一个线性序列，这个线性序列在生活正可以表示某些事情完成的相应顺序。如果说所求的图有回路的话，则不可能找到这个序列。
在大学数据结构课上，我们知道求拓扑排序的一种方法。首先用一个入度数组保存每个顶点的入度。在进行拓扑排序时，我们需要找到入度为0的点，将其存入线性序列中，再将其从图中删除（与它相关的边都删除，相邻的顶点的入度均减1），再重复上面的操作，直至所有的顶点都被找到为止。如果不对每次找入度为0的顶点的方法进行处理，而直接去遍历入度数组，则该算法的时间复杂度为O(|V|2)，如果使用一个队列来保存入度为0的顶点，则可以将这个算法的复杂度降为O(V+E)。
今天在算法导论上看了用dfs来求拓扑排序的算法，才发现其高深之处，膜拜之Orz…
下面是算法导论的叙述：
本节说明了如何运用深度优先搜索，对一个有向无回路图（dag）进行拓扑排序。对有向无回路图G=(V,E)进行拓扑排序后，结果为该图顶点的一个线性序列，满足如果G包含边（u, v），则在该序列中，u就出现在v的前面（如果图是有回路的，就不可能存在这样的线性序列）。一个图的拓扑排序可以看成是图中所有顶点沿水平线排列而成的一个序列。使得所有的有向边均从左指向右。因此，拓扑排序不同于通常意义上的排序。
在很多应用中，有向无回路图用于说明时间发生的先后次序，下图1即给出一个实例，说明Bumstead教授早晨穿衣的过程。他必须先穿好某些衣服，才能再穿其他衣服（如先穿袜子后穿鞋），其他一些衣服则可以按任意次序穿戴（如袜子和裤子），在图1中，有向边<u，v>表示衣服u必须先于衣服v穿戴。因此，该图的拓扑排序给出了一个穿衣的顺序。图2说明了对该图进行拓扑排序后，将沿水平线方向形成一个顶点序列，使得图中所有有向边均从左指向右。
拓扑排序算法具体步骤如下：
1、 调用dfs_travel()；
2、 在dfs_travel()每次调用dfs()的过程中，都记录了顶点s的完成时间，将顶点s按完成顺序保存在存放拓扑排序顺序的数组topoSort[]中。这样，该数组就存放了按先后顺序访问完成的所有顶点。
3、 最后拓扑排序得到的线性序列，即为topoSort[]的逆序。
现在我们分析一下时间复杂度，首先深度优先搜索的时间复杂度为O(V+E)，而每次只需将完成访问的顶点存入数组中，需要O(1)，因而总复杂度为O(V+E)。
可能有人会问，这样也行？别着急，现在给出它的证明：
证明：假设对某一已知有向无回路图G=(V,E)运行dfs_travel()过程，以便确定其顶点的完成时刻。只要证明对任一对不同顶点u、v∈V，若G中存在一条从u到v的边，则f[v]<f[u]。考虑过程dfs_travel()所探寻的任何边（u，v），当探寻到该边时，顶点v必然是已考察完成的顶点或者还未被访问到的顶点。若v是还未被访问到的顶点，则它是u的后裔，f[v]<f[u]。若v为已考察完成的顶点，则已完成探索，且f[v]已经设置了。因为仍在探寻u，还要为f[v]赋时间戳。一旦这么做后，就同样有f[v]<f[u]，这样一来，对于有向无回路图中任意边（u,v），都有f[v]<f[u]，从而定理得证。
简单解释：如果存在u到v的通路，则必然存在f[u]>f[v]，即u肯定在v的前面。如果还不理解的话，读者可能需要好好补充下深度优先搜索相关知识。
将上图顶点转化为数字：
代码如下（拓扑排序顺序与数组顺序逆序）：
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 using namespace std; 5 6 #define maxn 100 //最大顶点个数 7 int n, m; //顶点数，边数 8 9 struct arcnode //边结点 10 { 11 int vertex; //与表头结点相邻的顶点编号 12 arcnode * next; //指向下一相邻接点 13 arcnode() {} 14 arcnode(int v):vertex(v),next(NULL) {} 15 }; 16 17 struct vernode //顶点结点，为每一条邻接表的表头结点 18 { 19 int vex; //当前定点编号 20 arcnode * firarc; //与该顶点相连的第一个顶点组成的边 21 }Ver[maxn]; 22 23 void Init() //建立图的邻接表需要先初始化，建立顶点结点 24 { 25 for(int i = 1; i <= n; i++) 26 { 27 Ver[i].vex = i; 28 Ver[i].firarc = NULL; 29 } 30 } 31 32 void Insert(int a, int b) //插入以a为起点，b为终点，无权的边 33 { 34 arcnode * q = new arcnode(b); 35 if(Ver[a].firarc == NULL) 36 Ver[a].firarc = q; 37 else 38 { 39 arcnode * p = Ver[a].firarc; 40 while(p->next != NULL) 41 p = p->next; 42 p->next = q; 43 } 44 } 45 46 #define INF 9999 47 bool visited[maxn]; //标记顶点是否被考察，初始值为false 48 int parent[maxn]; //parent[]记录某结点的父亲结点，生成树，初始化为-1 49 int d[maxn], time, f[maxn]; //时间time初始化为0，d[]记录第一次被发现时，f[]记录结束检查时 50 int topoSort[maxn]; 51 int cnt; 52 void dfs(int s) //深度优先搜索（邻接表实现），记录时间戳，寻找最短路径 53 { 54 //cout << s << " "; 55 visited[s] = true; 56 time++; 57 d[s] = time; 58 arcnode * p = Ver[s].firarc; 59 while(p != NULL) 60 { 61 if(!visited[p->vertex]) 62 { 63 parent[p->vertex] = s; 64 dfs(p->vertex); 65 } 66 p = p->next; 67 } 68 time++; 69 f[s] = time; 70 topoSort[cnt++] = s; 71 72 } 73 void dfs_travel() //遍历所有顶点，找出所有深度优先生成树，组成森林 74 { 75 for(int i = 1; i <= n; i++) //初始化 76 { 77 parent[i] = -1; 78 visited[i] = false; 79 } 80 time = 0; 81 for(int i = 1; i <= n; i++) //遍历 82 if(!visited[i]) 83 dfs(i); 84 //cout << endl; 85 } 86 void topological_Sort() 87 { 88 cnt = 0; 89 dfs_travel(); 90 for(int i = cnt-1; i >= 0; i--) 91 cout << topoSort[i] << " "; 92 cout << endl; 93 } 94 int main() 95 { 96 int a, b, w; 97 cout << "Enter n and m："; 98 cin >> n >> m; 99 Init(); 100 while(m--) 101 { 102 cin >> a >> b; //输入起点、终点 103 Insert(a, b); //插入操作 104 } 105 topological_Sort(); 106 return 0; 107 }