algorithm - 如何使用不相交集检测无向图中的循环？

Question

算法:

For each edge (u, v) in the Adjacency list:
If u and v do not belong to the same set:
   Union(u, v)
else:
  return true // cycle detected
return false

图表:

(1)------(2)

邻接表:

[1] -> [2]

[2] -> [1]

不相交集:

{{1}, {2}}

迭代 1:

边 e = (1, 2)

并集(1, 2)

不相交集 = {{1, 2}}

迭代 2:

边 e = (2, 1)

2 和 1 属于同一个集合，因此算法检测到一个循环。很明显图中不包含环。

该算法适用于有向图。请帮我分析一下。

Answer 1

一个循环必须有不同的边缘!在联合查找算法中，您遍历所有边。您需要从邻接列表中过滤掉重复的边。在您的情况下，只有一次迭代，因此它会返回 false。