算法1.5 union-find并查集算法

算法1.5 union-find并查集

场景
当程序从输入中读取整数对(p,q)时,如果已知所有整数对都不能说明(p,q)是相连的,则输出整数对,否则忽略当前整数对,读取下一对.

1.5.1 union-find算法

API

import edu.princeton.cs.algs4.StdDraw;
import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;
public class UnionFind {
    private int[] id;//以触点为索引
    private int count;//分量个数
    public UnionFind(int N){
        count = N;
        id = new int[N];
        for(int i = 0; i<N; i++) id[i] = i;//开始每个分量只有一个触点
    }
    public int count(){ return count;}
    public boolean connected(int p, int q){
        return find(p) == find(q);
    }
    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;
        }
    }//union方法使得连通的触点对于的id[]值相同
    public static void main(String[] args){
        int N = StdIn.readInt();
        UnionFind uf = new UnionFind(N);
        while (!StdIn.isEmpty()){
            int p = StdIn.readInt();
            int q = StdIn.readInt();
            if(uf.connected(p,q)) continue;
            uf.union(p,q);
            StdOut.println(p + " " + q);
        }
        StdOut.println(uf.count + " components");
    }
}

要点

1. 主要实现在于维护一个整型数组id[],开始每个id[i]即代表一个连通的分量,元素值即索引值,共有N个,之后每union()两个触点p q,就让两个触点元素值都为q,最终一个分量中的元素id值都相等

特点

1. 无法处理大型问题:每一对输入union()都需要扫面整个id[]数组,算法增长级别为平方级别.

1.5.2 quick-union算法

import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;
public class QuickUnion {
    private int[] id;//以触点为索引
    private int count;//分量个数
    public QuickUnion(int N){
        count = N;
        id = new int[N];
        for(int i = 0; i<N; i++) id[i] = i;//开始每个分量只有一个触点
    }
    public int count(){ return count;}
    public boolean connected(int p, int q){
        return find(p) == find(q);
    }
    //回溯到根节点
    public int find(int p){
        while (id[p] != 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;
        count--;
    }//union方法使得连通的触点拥有相同的根节点
}

对比1.5.1

1. 基于同一组数据结构—以触点为索引的id[]数组
2. find()中,从给定触点开始,不断回溯到上一节点,直至初值的根节点pRoot,union()直接将另一节点的根节点qRoot赋值给id[pRoot]使得两个分量归并为一棵树

要点

1. union()的实现只用了一条语句就将一个根节点变为另一个根节点的父节点

特点

1. quick-union算法的成本依赖于输入,如果最坏情况:不断输入0-i整数对,此时为平方级别,而最佳情况可能是现象级别,不能保证quick-union算法始终快于quick-find

1.5.3 加权quick-union算法

import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;
public class WeightedQuickUnionUF {
    private int[] id;//父链接数组
    private int[] sz;//各个根节点对应分量大小
    private int count;//连通分量个数
    public WeightedQuickUnionUF(int N){
        count = N;
        id = new int[N];
        for(int i = 0; i < N; i++) id[i] = i;
        sz = new int[N];
        for(int i = 0; i < N; i++) sz[i] = 1;
    }
    public int count(){ return count;}
    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];}
        count--;
    }
}

对比1.5.2

1. 多了int[] sz用来保存各个根节点对应分量大小(不同树的大小)
2. union通过比较sz[find(p)]和sz[(q)]将小树连接到大树上

要点

1. sz[i]开始都初始化为1,一个触点
2. 将小树连接到大树上

特点

1. 加权算法中远离根节点的节点较少,只有一个节点被归并到大树中的情况很常见
2. 加权算法构造的森林中任意节点最多深度lgN,且最坏情况下find(),connected()和union()成本增长数量级为logN

1.5.4 路径压缩的加权quick-union算法(最优算法)

//压缩路径算法区别只在find()
    public int find(int p){
        int root = p;
        while (root != id[root]) root = id[root];//找到根节点
        while (root != p) {
            int temp = id[p];//temp暂存父节点作为下次循环的索引
            id[p] = root;//将当前节点直接连接到根节点
            p = temp;//还原索引
        }
        return root;
    }

同未压缩路径方法的联系区别

1. 只需要未find()增加一个循环,顺路将路径上遇到的节点都直接链接到根节点,最终可以得到几乎完全扁平化的树

特点

1. 理性状态下,我们希望每个节点都直接链接到它的根节点上,但又不想像quick-find一样修改大量链接,于是在检查节点的同时将它们直接链接到根节点

四种算法比较

(最坏情况下存在N个触点时成本的增长数量级)