algorithm - 强连通分量

Question

如果您不知道 SCC 算法的工作原理，请阅读这篇文章：https ://www.hackerearth.com/practice/algorithms/graphs/strongly-connected-components/tutorial/ （这是我能找到的最好的文章）。

在找到每个节点的完成时间后，我们反转原始图并从最高时间节点开始运行 DFS。如果我们从原始图中的最小节点开始运行 DFS 会怎样？为什么它不起作用？

Answer 1

那是因为第一个 DSF 的完成时间为您提供了拓扑顺序（这意味着一个边缘取决于另一个边缘）。SCC 意味着每个节点都可以从组件中的每个其他节点访问。如果你从最小的节点开始（如此落后），算法会给出错误的结果，因为在某个转置图的某个地方，它不会在两个实际连接的节点之间找到一条路，或者因为你之前“走过”一个节点而找到了一条不正确的路它的“父母”。

简单的例子（->手段取决于）。从 X 开始拓扑顺序：X,Y,Z,W

X -> Y   ->  Z
^   /
 \ ˘
  W

如果将上面的图转置并从 Z 开始，看起来整个图是一个 SCC。但事实并非如此。您必须在子元素之前处理父元素。因此，如果您从 X 开始，则不能在 Y 之前进入原始图中的 Z，也不能在 Y 之前进入 W。在转置图中，Z 和 Y 之间有一条路线，但只有在 invere 在那里时才能使用它原始图。并描述有或没有它。如果一个节点在拓扑上先于另一条路由，并且在它们之间的转置图中有一条路由，那么它们是强连接的。