有人能告诉我如何检查图的边是否形成循环吗?
任何信息都会非常有用。
多谢提前。
最佳答案
kruskal算法(您用它标记问题)使用disjoint set data structure初始化为每个顶点的不相交集。然后,对于每个边,合并边的顶点所属的两个集。如果两个顶点已经在同一个集合中,则找到一个循环。如果每次删除边,都会得到一个生成树如果按升序对边进行排序,这将是最小生成树。
如果您只需要知道一个图是否包含循环,那么可以使用一些更简单的方法作为dfs—如果任何节点有一个已经访问过的相邻节点(父节点除外)—您找到了一个循环。
关于algorithm - Kruskal算法:检查图的边缘是否形成循环的算法是什么?,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/21255433/