九、并查集-算法总结

九、并查集

9.1 简介

并查集用于处理不相交集合的合并与查询问题，常见操作有：

• 查询：查询元素属于哪个集合，可用于判断元素是否在一个集合中
• 合并：合并两个集合
  应用场景：动态连通性的判断，且不需要给出具体路径

9.2 数据结构

9.2.1 初始化

id数组存放的是结点的组号，初始化时将每个结点单独分为一组

private int[] id;public DisjoinSet(int size) {id = new int[size];for(int i = 0; i < size; i++)id[i] = i;
}

9.2.2 Quick-Find

由于使用整数表示结点，可以通过数组实现结点到组编号的映射

public void union(int p, int q) { // 获得p和q的组号int pID = id[p];int qID = id[q];// 如果两个组号相等，直接返回if (pID == qID) return;// 遍历一次，改变组号使他们属于一个组for (int i = 0; i < id.length; i++)if (id[i] == pID) id[i] = qID;count--;
}

9.2.3 Quick-Union

id数组存放的是结点的父节点索引，根节点的父节点是自身，通过这点判断能到达根结点

private int find(int p) { // 寻找p节点所在组的根节点，根节点具有性质id[root] = rootwhile (p != id[p]) p = id[p];return p;
}
public void union(int p, int q) { // Give p and q the same root.int pRoot = find(p);int qRoot = find(q);if (pRoot == qRoot) return;// 将一棵树(即一个组)变成另外一课树(即一个组)的子树id[pRoot] = qRoot;    count--;
}

9.2.4 Weighted Quick Union

保存两棵树的大小，每次将小的合并到大的树中