JAVAアルゴリズム3――連結性問題の高速合併アルゴリズムの重み付けバージョン

合併操作をする時、私達は勝手に第二の木を第一の木に接続するのではなく、ツリーごとのノード数を記録して、統合する時、いつもノード数の大きい木に結び目点数の少ない木を接続します.この変更には修正コードが少し多く必要であり、ノード数を保存するために配列が必要であるが、プログラムの効率を向上させるためには、このアルゴリズムを「加重高速合併アルゴリズム」と呼ぶ.

public class QuickUW
{
    public static void main(String[] args)
    {
        int N=Integer.parseInt(args[0]);
        int id[]=new int[N],sz[]=new int[N];
        for(int i=0;i<N;i++)
        {
            id[i]=i;
            sz[i]=1;
        }
        for(In.init();!In.empty();)
        {
            int i,j,p=In.getInt(),q=In.getInt();
            for(i=p;i!=id[i];i=id[i]);
            for(j=q;j!=id[i];j=id[j]);
            if(i==j) continue;
            if(sz[i]<sz[j])
            {
                id[i]=j;
                sz[j]+=sz[i];
            }
            else
            {    
                id[j]=i;
                sz[j]+=sz[j];
            }
        
    }
}

    重み付け急速結合アルゴリズムによって構築された森林は、無加重結合アルゴリズムにおけるツリーの経路よりもツリー内の経路が短い.最悪の場合、統合する集合のサイズは常に等しい(集合の大きさは2の冪).この木の構造は複雑に見えるが、2つのn乗接合点を持つ木の中で、樹根に到達するために必要な最大の接続数はnであるという単純な性質を持っている.
    性質:重み付け急速合併アルゴリズムは、N個のオブジェクトのうちの2つのオブジェクトが接続されているかどうかを判断し、せいぜい2 lgN条の連線を通過する.