我正在阅读算法导论。 22.5 Strongly Connected Component中，算法STRONGLY-CONNECTED-COMPONENT(G)定义为:
- 调用 DFS(G) 计算每个顶点 u 的完成时间 u.f
- 计算G转置
- 调用 DFS(G 转置)，但在 DFS 的主循环中，考虑按 u.f 递减顺序排列的顶点(如第 1 行中计算的那样)
- 将第3行形成的深度优先森林中每棵树的顶点作为单独的强连通分量输出
如果我将算法更改为仅使用 G，而不计算 G 转置。还要考虑按递增 u.f 顺序排列的顶点(拓扑排序的逆序):
- 调用 DFS(G) 计算每个顶点 u 的完成时间 u.f
- 调用 DFS(G)，但在 DFS 的主循环中，按照 u.f 递增的顺序考虑顶点(如第 1 行中计算的那样)
- 输出第2行形成的深度优先森林中每棵树的顶点
为什么这个算法错了？
最佳答案
你的问题其实是书上的习题22.5-3。此处给出了替代算法正确性的反例: http://sites.math.rutgers.edu/~ajl213/CLRS/Ch22.pdf
Professor Bacon’s suggestion doesn’t work out. As an example, suppose that our graph is on the three vertices {1, 2, 3} and consists of the edges (2, 1),(2, 3),(3, 2). Then, we should end up with {2, 3} and {1} as our SCC’s. However, a possible DFS starting at 2 could explore 3 before 1, this would mean that the finish time of 3 is lower than of 1 and 2. This means that when we first perform the DFS starting at 3. However, a DFS starting at 3 will be able to reach all other vertices. This means that the algorithm would return that the entire graph is a single SCC, even though this is clearly not the case since there is neither a path from 1 to 2 of from 1 to 3.
关于algorithm - 如果在计算强连通分量时不使用 G 转置怎么办？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/27086778/