有向无环图的拓扑排序

拓扑排序

对于一个有向无环图，我们可以这样确定一个图中顶点的顺序：

对于所有的u、v，若存在有向路径u-->v，则在最后的顶点排序中u就位于v之前。这样确定的顺序就是一个图的拓扑排序。

拓扑排序的特点：

（1）所有可以到达顶点v的顶点u都位于顶点v之前；

（2）所有从顶点v可以到达的顶点u都位于顶点v之后；

（3）只有有向无环图才存在拓扑排序；

（4）一个图的拓扑顺序不唯一

实现拓扑排序

思路

图中入度为0的点没有任何点可以到达它，因此可以排在最开始（若有多个入度为0的点，他们之间的相对顺序随意）；

因为入度为0的顶点已经排完序了，因此可以将那些入度为0的顶点去掉。去掉之后的图中，还会存在一些入度为0的顶点，因此可以继续采用上述的方法....

到最后图中还有一些入度均不为0的顶点，那么在这个图中从任意一个顶点开始走下去，必然会经过每个顶点多于1次，即存在环，与前提矛盾！

实现

拓扑排序常用的算法是通过一个队列存放入度为0的点，每次取出队列头元素，访问该顶点，然后然后将该点连接的所有边消除，再将新图的入度为0的点加入队列...直到图中不存在入度为0的点。

#define MAX_NODE 1000#define MAX_EDGE_NUM 100000struct Edge{int to;int w;int next;};Edge gEdges[MAX_EDGE_NUM];int gHead[MAX_NODE];bool gVisited[MAX_NODE];int gInDegree[MAX_NODE];int gEdgeCount;void InsertEdge(int u, int v, int w){int e = gEdgeCount++;gEdges[e].to = v;gEdges[e].w = w;gEdges[e].next = gHead[u];gHead[u] = e;gInDegree[v] ++;//入度加1}void TopoSort(int n /*节点数目*/){queue<int> zero_indegree_queue;for (int i = 0; i < n; i++){

if (gInDegree[i] == 0)zero_indegree_queue.push(i);}memset(gVisited, false, sizeof(gVisited));while (!zero_indegree_queue.empty()){int u = zero_indegree_queue.front();zero_indegree_queue.pop();gVisited[u] = true;//输出ufor (int e = gHead[u]; e != -1; e = gEdges[e].next){int v = gEdges[e].to;gInDegree[v] --;if (gInDegree[v] == 0){zero_indegree_queue.push(v);}}}for (int i = 0; i < n; i++){if (!gVisited[i]){//存在环！ 无法形成拓扑序}}}