将SCC格局变化，如果我们扭转图（使用Kosaraju的算法）？ [英] Will SCC pattern change if we reverse a graph(using Kosaraju's Algorithm)?

问题描述

假设我们有一个有向图，它不是一个完全图，并具有一个以上的SCC。 我不知道的强连通分量的变化模式，如果我们调换图形和使用Kosaraju的算法？ 说调换图我的意思是翻盖边缘的方向。 如果我们试图找到SCC的转/反转图形，而不是原来的，将在SCC我们发现是不同的？

Assume we have a digraph, it is not a complete graph and has more than one SCC. I wonder if the patterns of Strongly Connected Component changes if we transpose the graph and use Kosaraju's Algorithm? By saying "transpose the graph" I mean flip the direction of edges. If we try to find SCC in the transposed/reversed graph instead of the original, will the SCC we find be different?

我想出了这个问题，因为我误解了SCC的算法和我转/反转图形运行它。我得到的是相同的SCC正确的答案/它运行Kosaraju的算法。是否普遍适用于所有图表？

I came up with this question as I misunderstood the algorithm of SCC and runs it on my transposed/reversed graph. What I got is identical SCC to the correct answer/which runs Kosaraju's algorithm. Is it universally true to all graphs?

推荐答案

没有图形的SCC将即使当图形反转保持不变，这是在kosaraju的算法的SCC的非常重要的一点。只有SCC之间的链接被逆转。 Kosaraju的算法利用了这一事实，以评估DFS上反相图形现在给出SCC的哪个更接近水槽SCC更高完成时间值。由于水槽SCC没有出边，另一个SCC因此评估DFS上给出了SCC作为一个整体连接的组件，并且还允许图形分解成具有类似性质的子图上，我们再次申请DFS再弄SCC。

No the SCC of the graph will remain the same even when the graph is reversed and that is very important point in kosaraju's algorithm for SCC's. Only the links between SCC's are reversed. Kosaraju's algorithm leverages this fact to evaluate DFS on reversed graph which now gives higher finish time values for SCC's which are closer to the sink SCC. As Sink SCC has no outgoing edge to another SCC hence evaluating DFS on it gives out the SCC as whole connected component and also allows decomposition of graph into a subgraph with similar properties on which we again apply DFS to get another SCC.

这篇关于将SCC格局变化，如果我们扭转图（使用Kosaraju的算法）？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！