问在unDirected图中寻找强连通分量
EN

Stack Overflow用户

提问于 2017-06-16 16:38:32

回答 1查看 3.3K关注 0票数 3

我想在无向图中找到一个强连通的组件，也就是说，如果我从一个节点A开始，那么我将返回到节点A，并且每条边都被访问一次。

对于有向图，可以使用Tarjan的算法求强连通分量，但如何处理无向图。

发布于 2017-06-17 07:16:06

我想你很怀念强连接组件的含义。

强连通构件

如果在所有对顶点之间有一条路径，有向图是强连通的。有向图的强连通分量(SCC)是极大强连通子图。

但是，从您的定义到您所寻找的内容，我想说您希望在unDirected图中找到循环：

如果这只是您想要的，我会说，使用Dfs算法在unDirected图中查找循环。

希望我回答了你的问题

票数 4

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/44594132

复制

相似问题

问在unDirected图中寻找强连通分量EN