首页 > 代码库 > 《数据结构与算法分析：C语言描述》复习——第九章“图论”——拓扑排序
《数据结构与算法分析：C语言描述》复习——第九章“图论”——拓扑排序
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 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。