我知道可以使用 DFS 和 BFS 检测直接图中的循环。我想知道我们是否可以使用 检测有向图中的循环Union-Find 或不?
最佳答案
不,我们不能使用 union-find 来检测有向图中的循环。这是因为无法使用不相交集(执行联合查找的数据结构)来表示有向图。
当我们说“a union b”时,我们无法确定边的方向
但是,在无序图的情况下,每个连接的组件等效于一个集合。所以 union-find 可以用来检测循环。每当您尝试对属于同一连接组件的两个顶点执行并集时,我们可以说存在循环。
关于data-structures - 我们可以使用 Union-Find 数据结构检测有向图中的循环吗?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/61167751/