企业官网建设流程全解析

实际上，并查集通过维护一个由多棵树组成的森林来表示不相交的集合。每棵树中，任意节点与其父节点之间都具有“同属一个集合”的关系。通过对并查集进行初始化，并在需要时执行合并和查找操作，可以快速判断两个元素是否属于同一个集合，并且可以高效地合并不相交的集合。

并查集算法图解： 假设有5 个人 A、B、C、D E。A是B的朋友，B是C的朋友，D是E的朋友。

如我们所见：

1）A，B 和 C 相互连接

2）D 和 E 相互连接

因此，我们可以使用并查集这种数据结构来检查一个朋友是否直接或间接地连接到另一个朋友。我们还可以确定两个不同的断开连接的子集。这里有 2 个不同的子集是 { A ，B ，C } 和 { D ，E }。

可以在此处执行两个操作： 合并 （ A ，B ） - 连接两个元素 A 和 B。 查找 （ A ，B ） - 查找，是否有任何路径连接两个元素 A 和 B 例：你有一组元素 S = { 0 ，1 ， 2 ，3 ，4 ，5 ，6 ，7 ，8 ，9 }。这里有 10 个元素 （ N = 10 ）。我们可以使用数组 Arr 来管理元素的连接。Arr[ ] 由 set 的元素索引，大小为 N（作为集合中的 N 个元素），可用于管理上述操作（表示该元素的父节点）。

假设：仅当 Arr[A]=Arr[B] 时，A 和 B 对象才连接。 现在我们将如何实现上述操作： 查找 （A， B） - 检查 Arr[ A ] 是否等于 Arr[ B ]。 合并 （ A ，B ） - 将 A 连接到 B 并通过将所有值等于 Arr[ A ] 的元素更改为 Arr[ B] 来合并具有 A 和 B 元素。 最初有 10 个集合，每个集合都有一个元素。

当每个集合仅包含单个元素时，数组 Arr 为：

让我们执行一些操作： 1 ） 合并（ 2 ，1 ） Arr 数组将变成：

2 ） 合并（ 4 ，3 ）3 ） 合并（ 8 ，4 ）4 ） 合并（ 9 ，3 ） Arr 数组将变成：

可以看到，如果元素之间是相互连通的（从一个节点可以到达另一个节点），那么他们在同一棵树里，或者说在同一个集合里，他们的父节点是相同的。 这里合并操作有一个优化的点：如果我们树很深，比如说退化成链表，那么每次查询的效率都会非常低。所以我们要做一下路径压缩。也就是把树的深度固定为二。 这么做可行的原因是，并查集只是记录了节点之间的连通关系，而节点相互连通只需要有一个相同的祖先就可以了。