在无向图中寻找强连通分量

Question

3

我想在无向图中找到强连通分量，即如果我从节点 A 开始，则能回到节点 A，并且每条边恰好被访问一次。

对于有向图，可以使用Tarjan算法来查找强连通分量，但对于无向图该如何处理呢？

- Narendra Modi

4

在无向图的情况下，“strong”的部分毫无意义。按照定义的确切方式，尝试找出在图中从每个顶点可以到达哪些顶点吧。 - Anthony Labarre

@AnthonyLabarre 当然，无向图永远不能被称为“强连通”，但是在每个顶点之间都存在一条边的无向图应该怎么称呼呢？有什么算法可以找到这样的子图吗？我认为这就是被要求解决的问题。 - Khoi

1

@Khoi：你似乎在问与Narendra Modi不同的问题。每对顶点都相邻的无向图称为完全图或团，可以通过枚举所有固定大小的子集来找到它们（例如参见Wikipedia）。Narendra Modi似乎想要找到一个欧拉回路。 - Anthony Labarre

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Gefen Morami · Accepted Answer

我认为您对“强连通分量”的含义有所误解。

强连通分量

如果一个有向图中，所有顶点之间都存在一条路径，则该图是强连通的。该图的强连通分量是指最大的强连通子图。

但是，根据您的定义和需求，我认为您想要在无向图中找到循环：

如果您只需要这个功能，我建议使用DFS算法在无向图中查找循环。

希望我的回答能够解决您的问题。