本文介绍了我们可以使用 Union-Find 数据结构检测有向图中的循环吗?的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

我知道可以使用 DFS 和 BFS 检测直接图中的循环.我想知道我们是否可以使用 Union-Find 检测有向图中的循环?

I know that one can detect cycles in direct graphs using DFS and BFS. I want to know whether we can detect cycles in directed graphs using Union-Find or not?

  • 如果是,那么如何?和
  • 如果我们不能,那为什么?

推荐答案

不,我们不能使用 union-find 来检测有向图中的循环.这是因为无法使用不相交集(执行联合查找的数据结构)来表示有向图.

No, we cannot use union-find to detect cycles in a directed graph. This is because a directed graph cannot be represented using the disjoint-set(the data structure on which union-find is performed).

当我们说'a union b'时,我们无法确定边的方向

When we say 'a union b' we cannot make out the direction of edge

  1. a 会去 b 吗?(或)
  2. b 要去 a 吗?

但是,在无序图的情况下,每个连接的组件都相当于一个集合.所以 union-find 可以用来检测循环.每当您尝试对属于同一连通组件的两个顶点执行并集时,我们就可以说存在循环.

But, incase of unordered graphs, each connected component is equivalent to a set. So union-find can be used to detect a cycle. Whenever you try to perform union on two vertices belonging to the same connected component, we can say that cycle exists.

这篇关于我们可以使用 Union-Find 数据结构检测有向图中的循环吗?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!

05-18 04:30