动态连通性问题之快速查找算法笔记

快速查找（贪心算法）

目的：通过并查集解决动态连通性问题

定义： 在一个N个元素的数组中，当且仅当 p、q的id相等时，p和q是连通的。

课程链接
github地址

接口

/**
 * 判断两个元素是否连通： 比对id值是否相等即可
 */
public boolean connected(int p, int q)；


/**
 * 连通p、q
 * 将所有与p相同id的元素的id值都变更为q的id值
 */
public void union(int p, int q)；

算法实现

/**
 * 动态联通问题之快速查找（贪心算法）
 *
 * 定义: 在一个N个元素的数组中，当且仅当 p、q的id相等时，p和q是连通的。
 *
 */
public class QuickFindUF {

    private int[] id ;

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

    /**
     * 判断p、q是否连通
     * @param p
     * @param q
     * @return
     */
    public boolean connected(int p, int q) {
        return id[p] == id[q];
    }

    /**
     * 连通p、q
     * 将所有与 p 相同 id 的元素的 id 值 都变更为 q 的 id 值
     * @param p
     * @param q
     */
    public void union(int p, int q) {
        int pid = id[p];
        int qid = id[q];
        for (int i = 0; i < id.length; i++) {
            if (id[i] == pid ) id[i] = qid;
        }
    }

    public static void main(String[] args) {
        QuickFindUF quickFindUF = new QuickFindUF(10);
        quickFindUF.union(0,5);
        quickFindUF.union(5,6);
        quickFindUF.union(1,2);
        quickFindUF.union(2,7);
        quickFindUF.union(8,3);
        quickFindUF.union(3,4);
        quickFindUF.union(4,9);

        System.out.println(quickFindUF.connected(1,3));
        System.out.println(quickFindUF.connected(8,9));
    }

}

算法效率：

image

总结

查询速度为1（即直接比对元素的id值即可），但进行N次连通操作的时间复杂度为指数级增长，速度太慢。