data-structures - 我们可以使用 Union-Find 数据结构检测有向图中的循环吗?
问题描述
我知道可以使用 DFS 和 BFS 在直接图中检测循环。我想知道我们是否可以使用Union-Find检测有向图中的循环?
- 如果是,那么如何?和
- 如果我们不能,那为什么?
解决方案
不,我们不能使用 union-find 来检测有向图中的循环。这是因为无法使用不相交集(执行并集查找的数据结构)来表示有向图。
当我们说“a union b”时,我们无法确定边缘的方向
- 是a去b吗?(或者)
- b会去a吗?
但是,在无序图的情况下,每个连接的组件都等效于一个集合。所以 union-find 可以用来检测一个循环。每当您尝试对属于同一连通分量的两个顶点执行联合时,我们可以说存在循环。
推荐阅读
- excel - 计算非空白单元格以进行平均计算(不在范围内)
- javascript - 如何摆脱nodejs中try-catch块中的语法错误
- azure - EventHubConsumerClient Apache Qpid 内存泄漏?
- r - R tidyverse 警告:`[`()` 的`i` 参数不能是 tibble 3.0.0 的矩阵
- keras - 设置多站点 LSTM
- excel - 如果满足条件,计算单元格的平均值
- python - 如何为动态 Flask 端点创建 Swagger 文档?
- spring-boot - Spring Boot + Gradle 测试未运行
- flutter - 如何让 Flutter 容器从屏幕的左边缘开始?
- flutter - 从 imap 下载附件:BODY[1.3.1.2] 和 BODY.PEEK[1.3.1.2] 返回 null