关于算法:Algorithms-普林斯顿知识点熟记-UnionFind

Dynamic connectivity (动静连通性)

We assume “is connected to” is an equivalence relation

• 自反性 Reflexive:

    p is connected to p.

• 对称性 Symmetric:

    if p is connected to q, then q is connected to p.

• 传递性 Transitive:

   if p is connected to q and q is connected to r, then p is connected to r.

Quick Find (eager algorithm)

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 p_root = id[p];
        int q_root = id[q];
        for (int i = 0; i < id.length; i++) {if (id[i] == p_root){id[p] = q_root;
            }
        }
    }
}

Takes N^2 array accesses to process sequence of N union commands on N objects.(quadratic time is much to slow)

Quick Union (lazy approach)

package com.algorithm.week1;

public class QuickUnionUF
{private int[] id;

    public QuickUnionUF(int N)
    {id = new int[N];
        //  设置每个对象的 id 为本人的初始索引（n 次数组拜访）for (int i = 0; i < N; i++) {id[i] = i;
        }
    }

    private int root(int i)
    {//  id[i] 是 i 的父节点，一直获取父节点直到达到根节点（获取的父节点不再变动）// 数组的拜访次数取决于 i 的父节点的深度
        //     7
        //    / \
        //   3   4
        //  / \   \
        // 5   6   1
        // 例如上图 i 为 5 时父节点深度为 3 
        // 过程如下
        // i: 5 id[5]: 3  =>  i: 3 id[3]: 7  =>  i: 7 id[7]: 7  =>  return 7
        while (i != id[i]){i = id[i];
        }
        return i;
    }

    public boolean connected(int p, int q)
    {
        // 查看 p 和 q 两者的根节点是否统一
        // 数组的拜访次数取决于 p 和 q 父节点的深度
        return root(p) == root(q);
    }

    public void union(int p, int q)
    {
        // 数组的拜访次数取决于 p 和 q 父节点的深度
        int p_root = root(p);
        int q_root = root(q);
        // 将 p 的根节点指向 q 的根节点（p 和 q）id[p_root] = q_root;
    }
}

Quick-find 毛病

• Union 动作消耗较大（N 次）
• Trees 扁平，然而维持扁平的代价太大（须要 for 循环遍历更新每个元素更新父节点）

Quick-union 毛病

• Trees 能够变得相当高
• Find 代价太大（可能达到 N 次）