快速查找（貪心算法）

目的：通過(guò)并查集解決動(dòng)態(tài)連通性問(wèn)題

定義： 在一個(gè)N個(gè)元素的數(shù)組中，當(dāng)且僅當(dāng) p、q的id相等時(shí)，p和q是連通的。

課程鏈接
github地址

接口

/**
 * 判斷兩個(gè)元素是否連通： 比對(duì)id值是否相等即可
 */
public boolean connected(int p, int q)；


/**
 * 連通p、q
 * 將所有與p相同id的元素的id值都變更為q的id值
 */
public void union(int p, int q)；

算法實(shí)現(xiàn)

/**
 * 動(dòng)態(tài)聯(lián)通問(wèn)題之快速查找（貪心算法）
 *
 * 定義: 在一個(gè)N個(gè)元素的數(shù)組中，當(dāng)且僅當(dāng) p、q的id相等時(shí)，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

總結(jié)

查詢速度為1（即直接比對(duì)元素的id值即可），但進(jìn)行N次連通操作的時(shí)間復(fù)雜度為指數(shù)級(jí)增長(zhǎng)，速度太慢。