寻找无向图中的强连通分量
我想在无向图中找到一个强连通分量，即如果我从一个节点a开始，那么我将回到节点a，并且每个边都被精确地访问一次。
对于有向图，可以用Tarjan算法求强连通分量，但是对于无向图，该怎么办。
共有1个答案
我想你没有理解强连接成分的含义。
强连通分量
一个有向图是强连通的，如果所有对顶点之间都有一条路径。有向图的强连通分量(SCC)是最大强连通子图。
-
我的书定义了一种在线性时间内寻找有向图强连通分量的方法。另外，其他几种寻找强连通分量的算法（如Tarjan算法）也能在线性时间内找到强连通分量。
-
设，一个无向连通图，完全没有桥。描述了一种引导边的算法，使得新图是一个SCC。 我建议的算法 所以我们从任意顶点运行DFS。我们注意到，由于它是一个无向图，所以只有树边和后边（对吗？）。我们相应地连接边（一个树边将被引导为“向下”，一个后边将被引导为“向上”）。 谢谢
-
我正在努力自学图论，现在试图理解如何在图中找到SCC。我读过关于SO的几个不同的问题/答案（例如，1、2、3、4、5、6、7、8)，但我找不到一个可以遵循的完整的一步一步的例子。 根据CORMEN（算法导论），一种方法是： 调用DFS(G)计算每个顶点u的完成时间f[u] 计算转置(G) 调用DFS（转置(G))，但在DFS的主循环中，按F[u]递减的顺序考虑顶点（如步骤1中计算的那样） 输出步骤
-
我试着用谷歌搜索，但是没有任何有价值的东西弹出。 图表： 它是无方向的 表示为具有双边的有向图 可能包含具有负权重的边 我知道我可以使用Bellman Ford在有向情况下解决这个问题，但是对于无向边，它只返回单边（2个循环）作为其输出。我需要找到一个循环的大小 此外，该算法应该具有运行时复杂性O（V*E）和内存复杂性O（V）。
-
我在读关于BFS和DFS的图算法。当我在分析用DFS寻找图中强连通分量的算法时，我产生了一个疑问。为了寻找强连通分量，book（Coremen）首先在图上运行DFS，以得到顶点的完成时间，然后在图的转置上按照第一个DFS得到的完成时间的递减顺序运行DFS。但是我不能理解为什么第二个DFS必须按照完成时间运行。我的意思是，即使我们直接在图的转置上运行DFS（忽略完成时间），它也会给我们连接的组件吗？