2

我知道前者是一种数据结构，而后者是一种数学结构。

但在实施时，它们似乎具有许多相同的特性和行为。

不相交集中的每个元素都可以被认为是图中的一个顶点。图中的边表示 Union-Find 中的集合。

在查看http://algs4.cs.princeton.edu/15uf/和http://algs4.cs.princeton.edu/42digraph/

我相信两者都可以回答以下问题：

  • 这两个元素/顶点是否连接？
  • 有循环吗？

那么我没有看到的两者之间有更大的区别吗？我什么时候应该选择使用其中一种？

我看到图形算法可以在内部使用 Union-Find 结构 http://algs4.cs.princeton.edu/43mst/KruskalMST.java.html

一个实现细节，但如果联合查找更快，为什么要使用深度优先搜索来测试循环？http://algs4.cs.princeton.edu/44sp/DirectedCycle.java.html

4

1 回答 1

3

union find 是一种用于动态连接问题的数据结构，例如，当您在运行时将边一个接一个连接并想知道是否存在连接时。想想迷宫或液体渗透。此外，在动态连接问题中，您通常要处理不同项目的集合。您实际上是在构建等价类。然而，在许多图形问题中，您正在寻找一条路径或一个连接的组件。

因此，要回答您的问题，如果您正在处理不相交的集合或添加/删除边的问题，并且想查看系统何时连接或有多少连接项，请使用 union-find。否则，像 DFS/BFS 这样的图算法可能会更快、更容易实现。

于 2016-10-11T03:10:36.927 回答