使无向图成为强连通分量(SCC)
设G(V，E)，一个无向连通图，完全没有桥。描述了一种引导边的算法，使得新图是一个SCC。
我建议的算法
所以我们从任意顶点运行DFS。我们注意到，由于它是一个无向图，所以只有树边和后边（对吗？）。我们相应地连接边（一个树边将被引导为“向下”，一个后边将被引导为“向上”）。
谢谢
共有1个答案
你要找的是Robbins定理的证明。
关于更正式的证明，你可以看这篇文章（参见定理2的证明）。
下面不是一个正式的证明，但它是你可以想到的一种方式：
正如你已经提到的，由于没有桥，每一个边缘都是某个循环的一部分。由于您希望您的输出图是SCC，因此该输出图上的DFS（来自任何顶点）必须只有后边和树边。它不能有前向边或交叉边。
下面是一个简单的图表来帮助您了解这些情况。
-
我想在无向图中找到一个强连通分量，即如果我从一个节点开始，那么我将回到节点，并且每个边都被精确地访问一次。 对于有向图，可以用Tarjan算法求强连通分量，但是对于无向图，该怎么办。
-
输出应该如下所示： 我甚至不知道为什么会有这样的错误。我将代码从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（忽略完成时间），它也会给我们连接的组件吗？
-
如果您不知道SCC算法是如何工作的，请阅读本文：https://www.hackerearth.com/practice/algorithms/graphs/strong-connected-components/tutorial/（这是我能找到的最好的文章）。 在找到每个节点的完成时间后，将原图反转，从时间最高的节点开始运行DFS。如果我们从原始图中最小的节点开始运行DFS呢？为什么不管用？