找到一个在无向图的强连通组件

Question

我想找到无向图即一个强连接组件如果我从一个节点A开始，然后我将回到节点A和每个边通过一次访问完全相同。

For Directed Graph可以使用Tarjan算法找到强连通的组件，但是如何处理无向图。

Answer 1

我想你很想理解强连接组件的含义。

强连通分量

有向如果有所有顶点对之间的路径图形是强烈地连接。有向图的强连通分量（SCC）是最大强连通分图。

但是，从定义到你想找的，我说你想找个周期无向图：

• 进入每一次

• 你可以从节点开始节点并在节点A中完成。

如果只是你要找的东西，我会说使用Dfs算法来查找unDirected图中的循环。

希望我回答你的问题