强连通分量拟合法
如果您不知道SCC算法是如何工作的，请阅读本文：https://www.hackerearth.com/practice/algorithms/graphs/strong-connected-components/tutorial/（这是我能找到的最好的文章）。
在找到每个节点的完成时间后，将原图反转，从时间最高的节点开始运行DFS。如果我们从原始图中最小的节点开始运行DFS呢？为什么不管用？
共有1个答案
这是因为第一个DSF的完成时间给出了拓扑顺序（这意味着一条边依赖于另一条边）。SCC意味着每个节点都可以从组件中的每个其他节点到达。如果你从最小的节点开始（如此向后），算法将给出错误的结果，因为在转置图中的某个地方，它无法在两个实际连接的节点之间找到一条路，或者因为你在它的“父节点”之前“走过”一个节点而找到一条不正确的路。
简单示例(->表示依赖）。从X开始的拓扑顺序:X，Y，Z，W
X -> Y -> Z
^ /
\ ˘
W
如果你转置上面的一个，从Z开始，它看起来就像整个图是一个SCC。但事实并非如此。必须在子元素之前处理父元素。所以如果你从X开始，你不能在Y之前进入原图中的Z，也不能在Y之前进入W。在转置图中，在Z和Y之间有一条路线，但你只能在原图中有逆的情况下使用它。并描述有或没有它。如果一个节点在拓扑上先于另一条路由，并且在它们之间的转置图中存在一条路由，则它们是强连通的。
-
输出应该如下所示： 我甚至不知道为什么会有这样的错误。我将代码从https://www.geeksforgeeks.org/tarjan-algorithm-find-strong-connected-components/改为我的代码，并添加了input机会。我问过这个问题，一个朋友说：“这是addEdge方法中添加w后的两个代码的输出，在您的代码中w添加到所有元素中，而在原始代码中只添加到图V
-
在本章的剩余部分，我们将把注意力转向一些非常大的图。我们将用来研究一些附加算法的图，由互联网上的主机之间的连接和网页之间的链接产生的图。 我们将从网页开始。 像 Google 和 Bing 这样的搜索引擎利用了网页上的页面形成非常大的有向图。 为了将万维网变换为图，我们将把一个页面视为一个顶点，并将页面上的超链接作为将一个顶点连接到另一个顶点的边缘。 Figure 30 展示了从 Luther C
-
我在读关于BFS和DFS的图算法。当我在分析用DFS寻找图中强连通分量的算法时，我产生了一个疑问。为了寻找强连通分量，book（Coremen）首先在图上运行DFS，以得到顶点的完成时间，然后在图的转置上按照第一个DFS得到的完成时间的递减顺序运行DFS。但是我不能理解为什么第二个DFS必须按照完成时间运行。我的意思是，即使我们直接在图的转置上运行DFS（忽略完成时间），它也会给我们连接的组件吗？
-
我想在无向图中找到一个强连通分量，即如果我从一个节点开始，那么我将回到节点，并且每个边都被精确地访问一次。 对于有向图，可以用Tarjan算法求强连通分量，但是对于无向图，该怎么办。
-
我正在努力自学图论，现在试图理解如何在图中找到SCC。我读过关于SO的几个不同的问题/答案（例如，1、2、3、4、5、6、7、8)，但我找不到一个可以遵循的完整的一步一步的例子。 根据CORMEN（算法导论），一种方法是： 调用DFS(G)计算每个顶点u的完成时间f[u] 计算转置(G) 调用DFS（转置(G))，但在DFS的主循环中，按F[u]递减的顺序考虑顶点（如步骤1中计算的那样） 输出步骤
-
设，一个无向连通图，完全没有桥。描述了一种引导边的算法，使得新图是一个SCC。 我建议的算法 所以我们从任意顶点运行DFS。我们注意到，由于它是一个无向图，所以只有树边和后边（对吗？）。我们相应地连接边（一个树边将被引导为“向下”，一个后边将被引导为“向上”）。 谢谢