如果在计算强连通分量时不使用 G 的转置，会有什么影响？

Question

我正在阅读《算法导论》。在22.5强连通分量中，算法STRONGLY-CONNECTED-COMPONENT(G)定义为：

1. 调用DFS（G）计算每个顶点u的完成时间u.f
2. 计算G的转置
3. 调用DFS（G的转置），但在DFS的主循环中，按u.f（如第1行中计算的）递减的顺序考虑顶点
4. 将第3行形成的深度优先森林中每个树的顶点作为单独的强连通分量输出

如果我将算法更改为仅使用G，而不计算G的转置。同时按照递增的u.f（拓扑排序反向顺序）考虑顶点：

1. 调用DFS（G）计算每个顶点u的完成时间u.f
2. 调用DFS（G），但在DFS的主循环中，按递增的u.f（如第1行中计算的）顺序考虑顶点
3. 输出第2行中形成的深度优先森林中每个树的顶点

为什么这个算法是错误的？

- SmellyPanda

---

你的问题更适合在http://cs.stackexchange.com发问。 - SSC

Answer 1

你的问题实际上是书中的练习22.5-3。这里给出了一个证明你替代性算法不正确的反例：http://sites.math.rutgers.edu/~ajl213/CLRS/Ch22.pdf

Bacon教授的建议行不通。以一个三个顶点{1，2，3}的图为例，它由边(2,1)，(2,3)，(3,2)组成。然后，我们应该得到{2，3}和{1}作为我们的强连通分量。然而，DFS从2开始可能会在1之前探索3，这意味着3的完成时间比1和2更短。这意味着当我们首先执行DFS从3开始时。然而，从3开始的DFS将能够到达所有其他顶点。这意味着算法会返回整个图是单个强连通分量，尽管这显然不是情况，因为既不存在从1到2的路径，也不存在从1到3的路径。

- Dean Gurvitz

Answer 2

强连通分量中的顶点在定义上彼此连通（通过路径连接，不一定是直接边）。如果您在顶点X上进行第一次DFS调用，则可以找出“X连接到哪些顶点”（X->N）。为了确保所有这些顶点都与X相连（N->X），从而验证强连通性，您需要沿反向方向遍历边缘。这种最简单的方法是对图进行转置。

如果您正在寻找算法的证明，我相信您会找到一些。它可能不是最容易理解的，但请查看此来源，例如： 查找强连通分量的算法的正确性

- Kyborek