JavaScriptで蟻本 データ構造 Union-Find木判定

概要

アルゴリズムの学習記録を投稿します。
今回は蟻本・データ構造のUnion-Find木p94 についてです。

問題

以下２つのUnion-Find木を結合せよ

入力：
親:[0,1,1,0,6,1,6,4]
木の深さ:[0,1,1,0,2,1,2,2]

結果
親:[0,6,1,0,6,1,6,4]
木の深さ:[0,1,1,0,2,1,2,2]

図示

コード部分

    //
    /**
     *  Union-Find木の根を求める。
     * @param par{Array} 各要素のの親
     * @param x{Number} 求めたい要素
     */
    const  find = (par,x) =>{
        // 親と要素が一致する
        if(par[x] == x){
            console.log(`${par}|　| 親par[${x}]（=${par[x]}）と要素x（=${x}）が一致する場合、xを返す`)
            return x;
        }
        // 親と要素が一致しない場合、親を再帰的に探す
        else{
            console.log(`${par}|　| 親par[${x}]（=${par[x]}）と要素x（=${x}）が一致しない場合、親を再帰的に探す`)
            return par[x] = find(par,par[x]);
        }
    }
    //
    /**
     * Union-Find木を結合する
     * @param par{Array} 各要素のの親
     * @param rank {Array} 各要素の木の深さ
     * @param x{Number} 結合する要素1つ目
     * @param y{Number} 結合する要素2つ目
     */
    const  unite = (par, rank, x,y) =>{
        console.log(`par|rank|行動`);
        console.log(`--|---|---`)
        x = find(par,x);
        y = find(par,y);
        // 親が一致する場合、結合する必要がない
        if( x == y){
            console.log(`${par}|${rank}|親が一致しているため結合しないで終了する。`)
            return};

        //木の深さが深い方に結合する
        if(rank[x] < rank[y]){
            par[x] = y;
            console.log(`${par}|${rank}|1つ目の要素xより2つ目の要素yの木の深さが深いため、xの親をyに変更する。`);
        }else{
            par[y] = x;
            console.log(`${par}|${rank}|2つ目の要素yより1つ目の要素xの木の深さが深いため、yの親をxに変更する。`);
            if(rank[x] == rank[y]){rank[x] =  rank[x] + 1;}
        }
        console.log(`結合後の各要素の親:${par}`)
        console.log(`結合後の各要素の木の深さ:${rank}`)
    }
    
    var par,rank;
    par = [0,1,1,0,6,1,6,4]
    rank = [0,1,1,0,2,1,2,2]
    // par=[0,6,1,0,6,1,6,4] と表示される。
    unite(par,rank,6,1)

python tutor

コードを実際に動かせるwebサイト
ステップ実行かつステップ事の変数を確認できる特徴があります。

Python Tutorリンク

その他情報

感想

フリーハンドで図を書くのも理解が深まりますね

依存関係グラフ

依存関係グラフは変数の結びつきを一目でわかりやすくするための図です。
変数の流れを確認しやすくすることでワーキングメモリの負担を減らすことができます。
作成方法はコード上の変数に丸付けて線を繋げています。

状態遷移図

計算内容を明示する表。
ステップごとの変数の値を各列に表示します。
複雑な計算を行うコードを理解するのに役立つ表です。

par	rank	行動
0,1,1,0,6,1,6,4		親par[6]（=6）と要素x（=6）が一致する場合、xを返す
0,1,1,0,6,1,6,4		親par[1]（=1）と要素x（=1）が一致する場合、xを返す
0,6,1,0,6,1,6,4	0,1,1,0,2,1,2,2	2つ目の要素yより1つ目の要素xの木の深さが深いため、yの親をxに変更する。

参考資料

プログラミングコンテストチャレンジブック [第2版]　マイナビ　p84

プログラマー脳　秀和システム
p73 python tutor
p71 状態遷移表　
p69 依存関係グラフ

githubコミット部分