algorithm - 如果我们反转图形（使用 Kosaraju 算法），SCC 模式会改变吗？

Question

假设我们有一个有向图，它不是一个完整的图并且有多个 SCC。我想知道如果我们转置图形并使用 Kosaraju 算法，强连通分量的模式是否会发生变化？通过说“转置图形”，我的意思是翻转边缘的方向。如果我们尝试在转置/反转图中找到 SCC 而不是原来的，我们找到的 SCC 会不同吗？

我提出了这个问题，因为我误解了 SCC 的算法并在我的转置/反转图上运行它。我得到的是与正确答案相同的 SCC/它运行 Kosaraju 的算法。所有图表都普遍适用吗？

Answer 1

如果您查看http://en.wikipedia.org/wiki/Kosaraju%27s_algorithm，您会看到：

“转置图（每条边的方向反转的相同图）具有与原始图完全相同的强连通分量。”

（强连接组件是您可以从组件中的每个顶点到每个其他顶点的组件，如果您反转所有链接，这仍然会成立）。当然，连接不同组件的链接会颠倒过来，所以我希望你会得到组件以不同的顺序出现。

Answer 2

不，即使图形反转，图形的 SCC 也将保持不变，这是 kosaraju 的 SCC 算法中非常重要的一点。只有 SCC 之间的链接是反向的。Kosaraju 的算法利用这一事实来评估反向图上的 DFS，它现在为更接近汇 SCC 的 SCC 提供更高的完成时间值。由于 Sink SCC 没有到另一个 SCC 的出边，因此在其上评估 DFS 将 SCC 作为整个连接组件给出，并且还允许将图分解为具有相似属性的子图，我们再次应用 DFS 来获得另一个 SCC。