微客导航 » 文章资讯 » 强连通分量的 Tarjan 算法

强连通分量的 Tarjan 算法

2023-06-21 06:29:04 355

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

返回顶部
3162201930
czq8825@qq.com

强连通分量的 Tarjan 算法

输入和输出

算法

示例

热门推荐

随机推荐