拓扑排序：

对一个有向无环图（Directed Acyclic Graph,DAG）G进行拓扑排序，是将G中的所有顶点排成线性序列，使得图中任意一对顶点u和v，若边（u，v）属于G，则u在线性序列中出现在v之前。

如图：

一种可能的拓扑排序结果为：2->8->0->3->7->1->5->6->9->4->11->10->12.

程序实现：

 1 #include <iostream>
 2 #include <queue>
 3 #include <cstring>
 4 using namespace std;
 5 
 6 const int n = 13;
 7 int graph[n][n];
 8 int indegree[n] = {1,1,0,1,2,2,2,1,0,1,1,1,2};
 9 //结点数为n，用邻接矩阵graph[n][n]存储边权
10 //用indegree[i]存储每个节点的入度
11 void topologic(int* toposort){
12     int cnt = 0;//当前拓扑排序列表中有多少结点
13     queue<int> q;//保存入度为0的节点，还可以用栈甚至随机取
14     for(int i=0;i<n;i++){
15         if(indegree[i] == 0)
16             q.push(i);
17     }
18     int cur;//当前入度为0的节点
19     while(!q.empty()){
20         cur = q.front();
21         q.pop();
22         toposort[cnt++] = cur;
23         for(int i=0;i<n;i++){
24             if(graph[cur][i]!=0){
25                 indegree[i]--;
26                 if(indegree[i]==0)
27                     q.push(i);
28             }
29         }
30     }
31 }
32 int main()
33 {
34     memset(graph,0,sizeof(int)*n*n);
35     graph[0][6] = graph[0][1] = graph[0][5] = 1;
36     graph[2][0] = graph[2][3] = 1;
37     graph[3][5] = 1;
38     graph[5][4] = 1;
39     graph[6][4] = graph[6][9] = 1;
40     graph[7][6] = 1;
41     graph[8][7] = 1;
42     graph[9][10] = graph[9][11] = graph[9][12] = 1;
43     graph[11][12] = 1;
44     int toposort[n];
45     topologic(toposort);
46     for(int i=0;i<n;i++){
47         cout<<toposort[i]<<" ";
48     }
49     cout<<endl;
50     return 0;
51 }

运行结果：

转载请注明出处：http://www.cnblogs.com/gaobaoru-articles/