algorithm - 为什么保证反向图中post数最高的会在sink SCC？

Question

我想我现在明白了为什么我们不能保证原始图中最低的帖子编号是一个汇(它可能有到它之前已经访问过的顶点的出边)。

但为什么反转图表并查看最高帖子数的情况有所不同？为什么这是在原始图的汇 SCC 中查找顶点的万无一失的方法？

Answer 1

重要的是，对于由边 (A, B) 连接的两个强连通分量 A 和 B，即边入射 从 A 到 B，A 的最高帖子数总是会大于B 的最高帖子数。

从现在开始，我们将强连通分量 C 的最高后数表示为 h(C)。

But why is the case different for reversing the graph and looking at the highest post number? Why is this a foolproof way to find a vertex in the sink SCC of the original graph?

正如您所说，首先，您要查看最大 h(C)。根据第一段，入射到 C 上的所有边必须出，否则 h(C) 不会最大。

如果你现在反转这个图，所有入射到 C 上的边都必须是 incoming；他们只是被颠倒了。在 C 上运行深度优先搜索 (DFS)，将产生一棵现在只有 C 的顶点的树，因为它已被“隔离”并且是一个汇。 SCC 保留了在反转后从该 SCC 内的每个顶点 v 可以到达每个顶点 u 的属性，因此 SCC 的顶点不受影响。

现在第一个 SCC 已经建立，DFS 继续到具有第二高 h(D) 的 D。根据第一段，对于任何表示为 E 的 SCC，h(D) 大于 h(E)。只有 h(C) 大于 h(D)，但 C 的所有顶点都已被访问过!因此，D 是孤立的，就像 C 一样:连接 D 到任何 SCC E 的所有边都入射到 D，除了 C，所以 D 不是汇。不过 C 已经被访问过，所以 DFS 不会再次访问它。因此，整个 D 将被理解为另一个独立的、强连接的组件。

这个过程一直持续到最后一个 SCC 并产生一个森林，其中每棵树都对应一个强连接的组件。