九、并查集-算法总结

文章目录

• 九、并查集
• • 9.1 简介
  • 9.2 数据结构
  • • 9.2.1 初始化
    • 9.2.2 Quick-Find
    • 9.2.3 Quick-Union
    • 9.2.4 Weighted Quick Union

九、并查集

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] = root
    while (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

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