如果我不使用什么摹转计算强连通分量？ [英] What if I do not use G transpose in calculating Strongly Connected Components?

问题描述

我读算法导论。在22.5强连通分量，该算法强连接组分（G）的定义为：

I am reading Introduction to Algorithms. In 22.5 Strongly Connected Component, the algorithm STRONGLY-CONNECTED-COMPONENT(G) is defined as:

1. 呼叫DFS（G）来计算整理时间UF每个顶点u
2. 在计算摹置
3. 呼叫DFS（G转），但在DFS的主循环，考虑到顶点，以减少用友（如计算的1号线）
4. 输出在深度优先森林每棵树的形成第3行作为一个单独的强连通分量的顶点

如果我改变alogrithm只用G，不计算摹转。同时考虑到顶点，为了提高用友（逆序拓扑排序的）：

If I change the alogrithm to just using G, without calculating G transpose. Also consider the vertices in order of Increasing u.f(Reverse order of topological sort):

1. 呼叫DFS（G）来计算整理时间UF每个顶点u
2. 呼叫DFS（G），但在DFS的主循环，考虑到顶点，以增加UF（如计算的1号线）的
3. 输出在深度优先森林每棵树形成在第2行的顶点

为什么这个算法不对？

推荐答案

在强连接部件的顶点是由definiton，彼此连接（通过一个路径，不一定直接边缘）。如果你做的顶点x第一个DFS呼叫时，您发现哪些顶点为X连接（X - > N）。为了确保所有的顶点都连接到X（N - > X），因此，证实强连通你需要遍历的边缘朝相反的方向。做这样的最简单的方法是通过转图。

The vertices in strongly connected component are, by definiton, connected to each other (by a path, not necessarily by direct edge). if you make first DFS call on vertex X, you find out "which vertices is X connected to" (X -> N). To make sure that all those vertices are connected to X (N -> X) and therefore validate strong connectivity you need to traverse the edges in reversed directions. The easiest way to do such is by transposing the graph.

如果您要查找的算法证明，我相信你会找到一些。它可能不是最容易理解的，但检查这个来源，例如： 该算法的正确性查找强连通分量

If you look for proof of the algorithm, i am sure you will find some. It may not be the easiest to understand but check this source for example: Correctness of the algorithm for finding strongly connected components

这篇关于如果我不使用什么摹转计算强连通分量？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！