Java 并查集的实现
概念 其实并查集顾名思义就是有“合并集合”和“查找集合中的元素”两种操作的关于数据结构的一种算法。 用途 维护无向图的连通性。支持判断两个点是否在同一连通块内。 判断增加一条边是否会产生环：用在求解最小生成树的Kruskal算法里。 操作 并查集主要就三个操作：初始化、合并、查找 初始化 一般来说，并查集的初始化用数组即可，例如数组Tree[i]，i表示某节点，tree[i]表示当前节点的根节点 查找函数 这里的查找和java集合类List中的查找函数get()并不一样，他的作用是查找该节点的根节点，如果集合的parent等于集合的编号（即还没有被合并或者没有同类），那么自然返回自身编号。如果不同那么就可以调用递归函数。 代码如下 // 并查集查找根节点 static int findRoot(int x, int[] arr) { // 如果集合i的父亲是自己，说明自己就是源头，返回自己的标号 if (arr[x] == -1) return x; else // 否则查找集合i的父亲的源头 return findRoot(arr[x], arr); } 若需要在查找过程中添加路径压缩的优化，我们修改上面这个函数为： // 并查集查找根节点（优化算法,本质是将路径压缩了） static int findRootUseful(int x, int[] arr) { int res = 0; if (arr[x] == -1) return x; else { res = findRoot(arr[x], arr); arr[x] = res; // 将当前结点的双亲结点设置为查找返回的根结点编号 return res; } } ...