强连通分量的 Tarjan 算法
Tarjan算法用于查找有向图的强连通分量。实现这个算法只需要一次DFS遍历。
使用DFS遍历,我们可以找到森林的DFS树。从DFS树中,可以找到强连接的组件。当找到这种子树的根时,我们可以显示整个子树。该子树是一个强连接组件。
输入和输出
Input: Adjacency matrix of the graph. 0 0 1 1 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 Output: The strongly connected components: 4 3 1 2 0
算法
findComponent(u,disc,low,stack,stackItemFlag)
输入: 起始节点,发现时间,low,disc会保存顶点的发现时间,low会保存子树的信息。保存顶点的堆栈和另一个用于跟踪哪个节点在堆栈中的标志数组。
输出:显示SCC。
Begin time := 0 //不会为下一次函数调用初始化时间值 set disc[u] := time+1 and low[u] := time + 1 time := time + 1 push u into stack stackItemFalg[u] := true for all vertex v which is adjacent with u, do if v is not discovered, then fincComponent(v, disc, low, stack, stackItemFalg) low[u] = minimum of low[u] and low[v] else if stackItemFalg[v] is true, then low[u] := minimum of low[u] and disc[v] done poppedItem := 0 if low[u] = disc[u], then while u is not in the stack top, do poppedItem := top of stack display poppedItem stackItemFlag[poppedItem] := false pop item from stack done poppedItem := top of stack display poppedItem stackItemFlag[poppedItem] := false pop item from stack End
strongConComponent(graph)
输入&,减号; 给定的图表。
输出-所有强连接组件。
Begin initially set all items in the disc array to undiscovered for all elements in low to φ and mark no item is stored into the stack for all node i in the graph, do if disc[i] is undiscovered, then findComponent(i, disc, low, stack, stackItemFlag) End
示例
#include#include #define NODE 5 using namespace std; int graph[NODE][NODE] = { {0, 0, 1, 1, 0}, {1, 0, 0, 0, 0}, {0, 1, 0, 0, 0}, {0, 0, 0, 0, 1}, {0, 0, 0, 0, 0} }; int min(int a, int b) { return (a&stk, bool stkItem[]) { static int time = 0; disc[u] = low[u] = ++time; //最初发现时间和低值是1 stk.push(u); stkItem[u] = true; //在堆栈中标记为u for(int v = 0; v stk; for(int i = 0; i 输出结果 4 3 1 2 0