algorithm - 在有向图中，为什么使用完成时间而不是发现时间来确定强连通分量？

Question

在为有向图寻找强连通分量时，我们使用反向图中的完成时间作为顺序。为什么我们不能按降序使用发现时间？对我来说，它们看起来非常相似，都可以使用。然而，在我发现的所有逻辑中，他们只使用完成时间。

是否有任何示例表明它无法使用发现时间？

标签： algorithmgraphtheory

Answer 1

根据维基百科，关键不变量是“如果存在从 u 到 v 的正向路径，那么 u 将出现在 v 之前”。这表明我们寻找一个发现时间违反这一点的图表。例如，在图中

  _________
 /        _\|
a---->b---->c

a那时我们可能c会访问b，即使有一条从b到的路径c。然后我们遍历转置图并找到“强连通分量” {a}，然后{c, b}因为从c到有一条弧b。