1

到目前为止，我已经使用以下算法来查找图的强连通分量。

  1. 调用 DFS(G) 计算每个顶点 v 的完成时间 f[v]，将 G 的顶点按完成时间的降序排序；

  2. 计算 G 的转置 GT；

  3. 对 G 执行另一个 DFS，这次在主 for 循环中，我们按照 f[v] 的降序遍历 G 的顶点；

  4. 将 DFS 森林（由第二个 DFS 形成）中每棵树的顶点作为单独的强连通分量输出。

.

但我想知道是否有可能仅在一个 DFS 中找到所有强连接组件。

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

4

2 回答 2

2

我在强连接组件的维基百科页面上找到了这个：

Kosaraju 算法、Tarjan 算法和基于路径的强分量算法都有效地计算了有向图的强连通分量，但 Tarjan 和基于路径的算法在实践中受到青睐，因为它们只需要一次深度优先搜索而不是两次。

我认为这完全回答了你的问题:)

于 2012-10-23T15:11:04.753 回答
2

查看 Steven Skiena 的算法设计手册。它在一个 DFS 中计算 SCC。它基于最旧可达顶点的概念。

在开始时将每个顶点的可达顶点和 SCComponent# 初始化为自身。

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

在有向图上进行 DFS，您只对后边和交叉边感兴趣，因为这两条边会告诉您是否遇到后边并从另一个输入一个组件。

  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);
  }

因此，当您遇到这些边时，您会根据进入时间递归地设置可达顶点[]。if (class == BACK) { if (entry_time[y] < entry_time[ low[x] ] ) low[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 完成后（它的邻居的 DFS 也将完成），检查它的最低可达顶点：

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 被扫描，堆栈将有 a(bottom)->b->c(top).. pop 直到看到顶点 'a'。你得到一个'a'的SCC..同样你在一个DFS中得到所有连接的组件。

于 2012-10-23T23:13:31.790 回答