在一个DFS中查找Di-Graph中的强烈连接组件

Question

现在，我已经使用了以下算法来查找图的强连接组件。

1. 调用dfs（g）计算每个顶点V的完成时间F [V]，以减少完成时间的顺序对G的顶点进行排序；

2. 计算G;

的转置GT

3. 在G上执行另一个DFS，这次在主要的前循环中，我们通过G的顶点在f [v];

的降低顺序中

4. 在DFS森林中输出每棵树的顶点（由第二个DFS形成）作为单独强烈连接的组件。

。

但是我想知道是否可以在中找到所有强连接的组件。

在这方面的任何帮助都将不胜感激。

Answer 1

查看，史蒂文·斯凯那（Steven Skiena）的算法设计手册。它在一个DFS中计算SCC。它基于最古老的可到达顶点的概念。

初始化每个顶点的可触及顶点和sccomponent＃在开始时。

low[i] = i;
scc[i] = -1;

在Digraph上进行DFS，您仅对后边缘和横边很感兴趣，因为这两个边缘会告诉您您是否遇到了后边缘并从另一个遇到了1个组件。

  int edge_classification(int x, int y)
  {
    if (parent[y] == x) return(TREE);
    if (discovered[y] && !processed[y]) return(BACK);
    if (processed[y] && (entry_time[y]>entry_time[x])) return(FORWARD);
    if (processed[y] && (entry_time[y]<entry_time[x])) return(CROSS);
     printf("Warning: unclassified edge (%d,%d)n",x,y);
  }

因此，当您遇到这些边缘时，您会根据输入时间递归设置可触及的顶点[]。 如果（class == back）{ if（entry_time [y]＆lt; entry_time [low [x]]） 低[x] = y; }

if (class == CROSS) 
{
            if (scc[y] == -1)  /* component not yet assigned */
                    if (entry_time[y] < entry_time[ low[x] ] )
                            low[x] = y;
}

每当来自顶点'v'的最低可触及顶点本身时，就会发现一个新的紧密连接的组件（循环可以说，a-> b-> c-> a，a的最低可触及顶点是a）。

process_vertex_early(int v)
{
    push(&active,v);
}

完成顶点的dfs完成后（邻居的DF也已经完成），请检查最低的可触及顶点：

if (low[v] == v) 
{     /* edge (parent[v],v) cuts off scc */
          pop_component(v);
}
if (entry_time[low[v]] < entry_time[low[parent[v]]])
          low[parent[v]] = low[v];

pop_component（...）只是从堆栈中弹出，直到找到此组件。如果扫描a-> b-> c-> a，则堆栈将具有（底部） -> b-> c（top）.. pop直到看到顶点'a'。您将获得" A"的SCC ..同样，您可以在一个DF中获得所有连接的组件。

Answer 2

我在Wikipedia页面上找到了这一点，以进行强烈连接的组件：

Kosaraju的算法，Tarjan的算法和基于路径的强 组件算法都有效地计算了牢固连接的 有向图的组件，但塔琳（Tarjan）和基于路径的组件 算法在实践中受到青睐，因为它们仅需要 深度优先搜索而不是两个。

我认为这回答了您的问题：）