如果我们反转一个图(使用Kosaraju的算法)，SCC模式会改变吗？
提问于 2013-11-19 20:21:48
假设我们有一个有向图，它不是一个完整的图，并且有多个SCC。我想知道，如果我们转换图并使用Kosaraju算法，强连通组件的模式是否会发生变化？说“转图”，我指的是翻转边的方向。如果我们试图在转置/反置图中而不是原来的图中找到SCC，我们发现的SCC会有所不同吗？
我提出了这个问题，因为我误解了SCC的算法，并在我的转置/反转图上运行它。我得到的是相同的SCC正确的答案/运行Kosaraju的算法。它普遍适用于所有的图表吗？
回答 2
Stack Overflow用户
回答已采纳
发布于 2013-11-20 01:01:34
不，即使当图被反转时，图的SCC也将保持不变，这是kosaraju关于SCC的算法中非常重要的一点，只有SCC之间的链接才是反向的。Kosaraju的算法利用这一事实在反向图上评估DFS，该图为SCC提供了更高的完成时间值，后者更接近接收器SCC。由于Sink SCC没有向另一个SCC发出的边缘，因此对其进行DFS计算，将SCC作为整体连通分量，并允许将图分解成一个具有相似性质的子图，我们再次应用DFS来得到另一个SCC。
Stack Overflow用户
发布于 2013-11-19 21:47:36
如果您查看algorithm，您将看到：
“转置图(每个边的方向相反的相同图)与原图完全相同的强连通分量。”
(强连接组件是一个可以从组件中的每个顶点到每个其他顶点的组件，如果您反转所有链接，这仍然有效)。当然，连接不同组件的链接将被反转，所以我希望您能够得到不同顺序的组件。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/20087283
复制相关文章
腾讯云开发者
