算法笔记一

动态连接 并查集

• Union command 连接两个物体

• 网络，社交网络，

实现查找和合并

public class UF{
    UF(int N) // 初始化并查集

    void union(int p,int q) //在p和q之间添加分量

    boolean connected(int p, int q) //p和q之间连通吗？
}

快速查找 quick-find

p和q连通，则id[p]=id[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;
    }

    public boolean connected(int p,int q){
        return id[p] == id[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;
        }
    }
}

Quick-union[lazy approach]

• Interpretation: id[i] is parent of i

• Root of i is id[id[id[…id[i]…]]]

• Find : check if p and q have the same root

• Union : To merge compoents p and q,set the id of p’s root to the id of q’s root

public class QuickUnionUF{
    private int[] id;

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

    private int root(int i){
        while(i != id[i]) i = id[i]; //根节点 i = id[i]
        return i;
    }

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

    public void union(int p,int q){
        int i = root(p)
        int j = root(q);
        id[i] = j; //将q的根节点的id值赋为p的根节点id值
    }
}

Quick-Union improvements

• Weigthed quick-union

  • modify quick-union to avoid tall tree.
  • keep track of size of each tree(number of objects).
  • balance by linking root of smaller tree to root of larger tree.

• 数据结构：和quick-union一样，但是维护一个额外数组sz[i]来计算以i为根的树包含的对象个数。

• Find ： Identical to quick-union

• Union : 主要有两处改变

  • Link root of smaller tree to root of larger tree.
  • Update the sz[] array.

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 = root(p);
        int j = root(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、

Quick union with path compression

• just after computing the root of p,set the id of examined node to point to that root.

Two-pass implementation

• add second loop to root() to set the id[] of each examined node to the root.

Simpler one-pass variant

• Make every other node in path point to its grandparent(thereby halving path length)

private int root(int i){
    while(i != id[i]){
        id[i] = id[id[i]];
        i = id[i];
    }
    return i;
}