2014.07.04 17:23
简介：
我们考虑一种特殊的图：
1. 有向图
2. 只有一个连通分量
3. 不存在环
那么这样的图里，必然可以找到一种排序方式，来确定谁在谁的“前面”。
简单的来说可以这么理解：如果存在一条边a->b，那么a顶点就在b的前面。
下面我们通过例子来看看拓扑排序的过程，确定所有的顶点中，谁排在谁的前面。
图示：
下面是一个图，符合上面所提出的三个条件，因此可以进行拓扑排序。我们关注每个顶点的入度，表示这个顶点被指向的次数。
每次我们都选出一个入度为0的顶点，因为入度为0的顶点是没有被任何边指向的。“被指向”就代表排在后面。
比如从目前的图看来，C->E代表顶点E排在顶点C之后。
把入度为0的顶点去除后，同时去除包含它们的边。入度为0的顶点可能不止一个，所以这些点的排序也是并列的。
继续去掉入度为0的顶点并且把它们的排序记录下来，同时去掉对应的边。直至所有顶点都去掉为止。
当所有顶点都去掉了，排序也就完成了。
实际上，即使图的连通分量不止一个排序也可以进行，只是不同连通分量之间的排序是互不影响的。只要是无环有向图，都可以进行拓扑排序。
实现：
1 // A simple illustration for topological sort. Graph represented by adjacency matrix. 2 #include <iostream> 3 #include <queue> 4 #include <vector> 5 using namespace std; 6 7 void topologicalSort(const vector<vector<bool> > &graph, vector<int> &order) 8 { 9 int n; 10 int i, j; 11 vector<int> indegree; 12 queue<int> q; 13 14 n = (int)graph.size(); 15 indegree.resize(n, 0); 16 17 for (i = 0; i < n; ++i) { 18 for (j = 0; j < n; ++j) { 19 if (graph[i][j]) { 20 ++indegree[j]; 21 } 22 } 23 } 24 25 for (i = 0; i < n; ++i) { 26 if (indegree[i] == 0) { 27 q.push(i); 28 break; 29 } 30 } 31 32 while (!q.empty()) { 33 i = q.front(); 34 q.pop(); 35 order.push_back(i); 36 for (j = 0; j < n; ++j) { 37 if (graph[i][j] && (--indegree[j] == 0)) { 38 q.push(j); 39 } 40 } 41 } 42 43 indegree.clear(); 44 } 45 46 int main() 47 { 48 vector<vector<bool> > graph; 49 vector<int> order; 50 int n; 51 int nk; 52 int i, j; 53 int tmp; 54 55 while (cin >> n && n > 0) { 56 graph.resize(n); 57 for (i = 0; i < n; ++i) { 58 graph[i].resize(n, false); 59 } 60 61 for (i = 0; i < n; ++i) { 62 cin >> nk; 63 for (j = 0; j < nk; ++j) { 64 cin >> tmp; 65 graph[i][tmp] = true; 66 } 67 } 68 69 topologicalSort(graph, order); 70 71 if ((int)order.size() == n) { 72 for (i = 0; i < n; ++i) { 73 cout << order[i] << ‘ ‘; 74 } 75 cout << endl; 76 } else { 77 cout << "The graph has a cycle." << endl; 78 } 79 80 for (i = 0; i < n; ++i) { 81 graph[i].clear(); 82 } 83 graph.clear(); 84 order.clear(); 85 } 86 87 return 0; 88 }