给定图 G，可以使用以下算法找到 SCC：
DFS(G) // compute finish times f[u]
GT = Transpose(G)
DFS(GT) // considering vertices in order of decreasing f[u]
我想了解的是：为什么必须按照完成时间递减的顺序进行第二次 DFS，有没有办法证明这一点？为什么，例如，以递增顺序考虑顶点并不能计算正确的 SCC？
我已经在 SO 上阅读了一些答案和示例，但它们没有帮助。问题是如何证明这个事实。
谢谢
那么，你只想要一个反例吗？
让我们只取具有 2 个顶点（1 和 2）和一个从 1 到 2（但不是从 2 到 1）的链接的图。该图的 SCC 是 {1} 和 {2}。从 1 开始 DFS，我们到 2，这里 DFS 不能再扩展，所以 2 完成，1 完成，因为从 1 到 2 的唯一边。顺序是 2 ；1.让我们转置图，不要故意按照算法在2上启动转置图的DFS（我们应该从1开始）。从 2，我们可以在转置图上转到 1。DFS 给出 1 和 2 已选中，因此 {1, 2} 将是 SCC，尽管它不是 SCC。
这个反例证明了我们不能为第二个 DFS 取我们想要的顺序，但这并不能证明我们每次都会得到错误的结果。
例如，让我们取同一个图，其中包含 1 和 2 之间的链接，以及 2 到 1 之间的链接。该图的唯一 SCC 是 {1, 2}。让我们从 1 开始第一个 DFS。这也给出了命令 2 ；1. 现在，如果我们再次在 1 上启动转置图的 DFS，我们将得到 {1, 2} 作为 SCC。因此，对于这种情况，我们有参加的结果。
TL;DR：“获得好结果”和“按降序获取顶点”之间没有等价性。但后者暗示了前者。
好的，我知道了。完成时间的顺序是为了防止通过交叉边（原始图）访问组件外部的顶点，因为这些在转置图中连接 2 个节点u和vif d[u] < d[v]。
不过感谢您的回答。