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

Question

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

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

Answer 1

如果你看http://en.wikipedia.org/wiki/Kosaraju%27s_algorithm你会看到:

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

(强连通组件是指您可以从组件中的每个顶点到达每个其他顶点的组件，如果您反转所有链接，这仍然成立)。当然，连接不同组件的链接将被颠倒，所以我希望您能以不同的顺序获得组件。