有向无环图
     如果一个有向图的任意顶点都无法通过一些有向边回到自身，那么称这个有向图为有向无环图。 拓扑排序
     拓扑排序是将有向无环图G的所有顶点排成一个线性序列，使得对图G中的任意两个顶点u、v，如果存在边u->v，那么在序列中u一定在v前面，这个序列又被称为拓扑序列。 如下图：结点0和1没有前驱节点，可以任意访问，但是结点2必须在结点0和1访问完之后才能访问，同理结点3和4必须在结点2访问完以后才能访问，但是结点3和4 之间没有依赖关系，结点5必须在结点3和结点6访问之后才能访问，等等.....
因此，对于下图的一个拓扑序列可以是：0,1,2,3,4,6,5,7 也可以是：0,1,2,4,6,3,5,7
拓扑排序步骤如下：
（1）定义一个队列Q，并把所有入度为0的结点加入队列
（2）取队首结点，访问输出，然后删除所有从它出发的边，并令这些边到达的顶点的入度减1，如果某个顶点的入度减为0，则将其加入队列。
（3）重复进行（2）操作，直到队列为空。如果队列为空时入过队的结点数恰好为N，说明拓扑排序成功，图G为有向无环图；否则，拓扑排序失败，图G有环。
  有向无环图的拓扑排序算法，可用于对有依赖关系的行程或事件做先后排序。 代码如下： main.cpp #include #include #include using namespace std; void TopSort(vector> &G, int n, vector &inDegree) { int num = 0; queue q; for (int i = 0; i < n; ++i) { if (inDegree[i] == 0) { q.push(i); } } while (!q.empty()) { int u = q.front(); cout << u << " "; q.pop(); for (size_t i = 0; i < G[u].size(); ++i) { int v = G[u][i]; // v is the successor vertices of u inDegree[v]--; if (inDegree[v] == 0) { q.push(v); } } G[u].clear(); // clear all out edge of vertices u num++; } cout << endl; if (num == n) { cout << "topological sorting successed"; } else { cout << "there is a ring in the graph, can't do topological sorting"; } return; } int main() { int n, m; cout << "please enter # of vertices and edges: "; cin >> n >> m; vector> G(n); for (int i = 0; i < m; ++i) { int x, y; cout << "input the " << i+1 << " edge: "; cin >> x >> y; G[x].push_back(y); } cout << "the topological sorting is: " << endl; vector inDegree(n); for (auto x : G) { for (auto y : x) { inDegree[y]++; } } TopSort(G, n, inDegree); return 0; } 运行结果：