算法:
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 属于同一个集合,因此算法检测到一个循环。 很明显图中不包含环。
该算法适用于有向图。请帮我分析一下。
最佳答案
一个循环必须有不同的边缘!在联合查找算法中,您遍历所有边。您需要从邻接列表中过滤掉重复的边。在您的情况下,只有一次迭代,因此它会返回 false。
关于algorithm - 如何使用不相交集检测无向图中的循环?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/43438419/