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

Question

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

Answer 1

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

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