algorithm - Kruskal 算法：检查图的边缘是否形成循环的算法是什么？

Question

有人可以向我提供有关如何检查图形边缘是否形成循环的信息吗？任何信息都会非常有帮助。提前谢谢了。

Answer 1

Kruskal 算法（你用它来标记问题）使用不相交集数据结构初始化每个顶点的不相交集。然后，对于每条边，边的顶点所属的两个集合被合并。如果这两个顶点已经在同一个集合中，那么您已经找到了一个循环。如果每次发生时都删除边缘，您将得到一棵生成树。如果按照权重升序对边缘进行排序，那将是最小生成树。

如果您只需要知道图形是否包含循环，请使用更简单的 DFS - 如果任何节点具有已经访问过的相邻节点（父节点除外） - 您已经找到了一个循环。

Answer 2

它是使用快速联合查找数据结构来检查要连接的边是否不在同一集群的顶点之间。

并集数据结构

Answer 3

在图上做一个完整的 DFS。为图中的每个节点维护两个布尔变量，“已访问”和“已完成”。“visited”表示顶点是否已被访问，“completed”表示从该特定节点开始的 DFS 是否已完成。如果在进行 DFS 时遇到了一个已经访问过但 DFS 尚未完成的节点，则图中存在一个循环。