algorithm - 循环有向图和无向图

Question

如何检测循环中的

1. 有向图
2. 无向图。

对于无向图..我想到的一种算法是使用不相交集。

• 对于 G 中的每个顶点 v
  • 套装(v)
• 对于 G 中的每个边 e(u,v) 一个接一个
  • 如果查找集(u) == 查找集(v)
    • return true // 循环存在
• 返回假

Answer 1

对于无向的，只需使用 DFS：如果边缘指向已访问的顶点，则有一个循环。

对于有指导的人，请看一下这个问题。

Answer 2

您在无向图中找到循环的方法应该是这样的：

• 对于 G 中的每个顶点 v
  • Meke-set(v)
• 对于 G 中的每个边 e(u,v) 一个接一个
  • 如果查找集(u) == 查找集(v)
    • 返回真
  • 联合集（u，v）
• 返回假

对于有向图，您应该使用Tarjan 的强连通分量算法来获取图中强分量的数量。然后，您可以检查强连通分量数是否等于顶点数。因为如果有向图中存在环，那么同一个强连通分量中至少有两个顶点。这意味着如果有向图有环，则强连通分量的总数应小于顶点数。