• 暂时停更一段时间!
  • 近期网站将陆续进行前端页面改造!
  • 招募网站编辑,联系站长!

算法(三)union-find

文章目录[隐藏]

 

用于解决动态连通性问题,能动态连接两个点,并且判断两个点是否连通。

public class UF {
    private int[] id;

    public UF(int N) {
        id = new int[N];
        for (int i = 0; i < N; i++) {
            id[i] = i;
        }
    }

    public boolean connected(int p, int q) {
        return find(p) == find(q);
    }
}

quick-find

可以快速进行 find 操作,即可以快速判断两个节点是否连通。

同一连通分量的所有节点的 id 值相等。

但是 union 操作代价却很高,需要将其中一个连通分量中的所有节点 id 值都修改为另一个节点的 id 值。

public int find(int p) {
    return id[p];
}
public void union(int p, int q) {
    int pID = find(p);
    int qID = find(q);

    if (pID == qID) return;
    for (int i = 0; i < id.length; i++) {
        if (id[i] == pID) id[i] = qID;
    }
}

quick-union

可以快速进行 union 操作,只需要修改一个节点的 id 值即可。

但是 find 操作开销很大,因为同一个连通分量的节点 id 值不同,id 值只是用来指向另一个节点。因此需要一直向上查找操作,直到找到最上层的节点。

    public int find(int p) {
        while (p != id[p]) p = id[p];
        return p;
    }

    public void union(int p, int q) {
        int pRoot = find(p);
        int qRoot = find(q);
        if (pRoot == qRoot) return;
        id[pRoot] = qRoot;
    }

这种方法可以快速进行 union 操作,但是 find 操作和树高成正比,最坏的情况下树的高度为触点的数目。

加权 quick-union

为了解决 quick-union 的树通常会很高的问题,加权 quick-union 在 union 操作时会让较小的树连接较大的树上面。

理论研究证明,加权 quick-union 算法构造的树深度最多不超过 logN。

public class WeightedQuickUnionUF {
    private int[] id;
    // 保存节点的数量信息
    private int[] sz;

    public WeightedQuickUnionUF(int N) {
        id = new int[N];
        sz = new int[N];
        for (int i = 0; i < N; i++) {
            id[i] = i;
            sz[i] = 1;
        }
    }

    public boolean connected(int p, int q) {
        return find(p) == find(q);
    }

    public int find(int p) {
        while (p != id[p]) p = id[p];
        return p;
    }

    public void union(int p, int q) {
        int i = find(p);
        int j = find(q);
        if (i == j) return;
        if (sz[i] < sz[j]) {
            id[i] = j;
            sz[j] += sz[i];
        } else {
            id[j] = i;
            sz[i] += sz[j];
        }
    }
}

路径压缩的加权 quick-union

在检查节点的同时将它们直接链接到根节点,只需要在 find 中添加一个循环即可。

各种 union-find 算法的比较

 


丨极客文库, 版权所有丨如未注明 , 均为原创丨
本网站采用知识共享署名-非商业性使用-相同方式共享 3.0 中国大陆许可协议进行授权
转载请注明原文链接:算法(三)union-find
喜欢 (0)
[247507792@qq.com]
分享 (0)

邀请您免费 注册账号 登录 即可参与讨论!