拓扑排序
有向无环图的拓扑排序是顶点的线性排序。对于有向图的每条边UV,顶点u将在排序中出现在顶点v之前。
我们知道源顶点会在目标顶点之后,所以我们需要使用堆栈来存储之前的元素。完成所有节点后,我们可以简单地从堆栈中显示它们。
输入和输出
Input: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 1 0 0 0 0 1 0 1 0 0 0 Output: 拓扑排序后的节点: 5 4 2 3 1 0
算法
topoSort(u,visited,stack)
输入-起始顶点u,一个数组,用于跟踪访问或未访问哪个节点。用于存储节点的堆栈。
输出-在堆栈中按拓扑序列对顶点进行排序。
Begin mark u as visited for all vertices v which is adjacent with u, do if v is not visited, then topoSort(c, visited, stack) done push u into a stack End
performTopologicalSorting(Graph)
输入-给定的有向无环图。
输出-节点序列。
Begin initially mark all nodes as unvisited for all nodes v of the graph, do if v is not visited, then topoSort(i, visited, stack) done pop and print all elements from the stack End.
示例
#include#include #define NODE 6 using namespace std; int graph[NODE][NODE] = { {0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0}, {0, 0, 0, 1, 0, 0}, {0, 1, 0, 0, 0, 0}, {1, 1, 0, 0, 0, 0}, {1, 0, 1, 0, 0, 0} }; void topoSort(int u, bool visited[], stack &stk) { visited[u] = true; //设置为节点v被访问 for(int v = 0; v stk; bool vis[NODE]; for(int i = 0; i 输出结果 拓扑排序后的节点: 5 4 2 3 1 0