如果我在计算强连通分量时不使用G转置呢？

Question

我在读算法介绍。在22.5强连接组件中，算法强连接组件(G)定义为：

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

如果我把alogrithm改为只使用G，而不计算G转置。还要考虑按U.F增加的顺序（拓扑排序的逆序）排列的顶点：

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

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

Answer 1

你的问题实际上是书中的练习22.5-3。下面给出了一个反例来验证您的替代算法的正确性:http://sites.math.rutgers.edu/~ajl213/clrs/ch22.pdf

培根教授的建议行不通。作为一个例子，假设我们的图在三个顶点{1,2,3}上，并且由边（2,1）,（2,3）,（3,2）组成。然后，我们应该以{2,3}和{1}作为我们的SCC结束。但是，从2开始的DFS可能会在1之前探索3，这意味着3的完成时间低于1和2。这意味着当我们从3开始第一次执行DFS时。然而，从3开始的DFS将能够到达所有其他顶点。这意味着算法将返回整个图是单个SCC，尽管显然不是这样，因为从1到3中既没有从1到2的路径。