[AL]クルーズアルゴリズム(feat.最小拡張ツリー)-JavaScript

クルーズアルゴリズム(Kruskal Algorithm)は、グラフィック内のすべての頂点を最小限のコストで接続するためのアルゴリズムです.
図面内のすべての頂点を含み、ループのない接続線を描画する場合、重み付けと最小化を求める場合に使用します.すなわち,最小伸長木(MST)を求めるアルゴリズムである.
クルースカアルゴリズムを詳細に議論する前に,まず伸長木と最小伸長木について議論する.🏃‍♂️

ツリーを展開

生成ツリーは、グラフィックの最小接続部分を表します.

の最小接続は、幹線の数が最も少ないことを意味します.

グラフで、一部の幹線で作成されたツリーを選択します.

すべての頂点は、自転車を含めることはできません.

1の図には、複数の伸長ツリーが存在してもよい.

最小長ツリー

Minimum Spanning Tree(Minimum Spanning Tree)とは、上述した生成ツリーにおいて、接続される幹線の重み付けと最小のツリーのことである.

クルーズアルゴリズム

クルースカアルゴリズム(Kruskal Algorithm)は、上記の最小伸長木を求めるアルゴリズムであり、Greedy Algorithmの一種である.
⚡
Greedy Algorithm:現在の状況で最適なスキームを選択するアルゴリズム

インプリメンテーションプロセス

図中の幹線の重み

を昇順に並べる.

周期を形成する直線上で順次幹線

を選択する.

で選択した幹線をMSTコレクションに追加します.

この場合、周期が形成されたか否かを判断する方法、すなわちUnion Findアルゴリズムがある.
(追加する幹線の両端の頂点が同一集合かどうかを判断するため!!)

例題

問題の説明
n個の島の間に橋を建設する費用(費用)については、すべての島が最小の費用で互いに通行できるようにする解決策を完了し、必要な最小の費用を返してください.
せいげんじょうけん

島の個数nは1以上100以下である.

コストの長さは(n−1)*n)/2以下である.

の任意iについては、コスト[i][0]とコスト[i][1]は、橋を結ぶ2つの島の番号を含み、コスト[i][2]は、この2つの島を結ぶ橋を建設するのに必要な費用である.

すべての島間の橋梁建設費用は支払われません.この場合,二つの島の間に建設することは不可能であると考えられる.

に接続できない島を与えない.

I/O例
ncostsreturn4[[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]]4
I/O例説明
コストは下図のように、緑のパス接続を使用すると、すべての人が通過できるように最小限のコストで使用できます.

問題を解く

前述したように、「グラフの中の幹線の重みを昇順に並べる」、すなわちcosts[i][2]を基準として、まずcostsを並べる.

costs.sort((a,b)=>a[2]-b[2]);

そして、この問題に対して、ループ形成を決定するためのUnion−Findアルゴリズムが実施される.

// 처음에는 자기 자신의 값을 부모로 가지는 배열 생성
const parent = [];
for(let i=0; i<n; i++) parent.push(i);

// 각 섬의 부모를 찾는 재귀 함수
// 만약 초기 값이 아니라면 parent[x]를 이용해 위로 올라가서 부모값 찾음
const getParent = (parent, x) => {
  if(parent[x] === x) return x;
  return parent[x] = getParent(parent,parent[x]);
}

// 두 섬의 부모를 하나로 합쳐준다.
// 이때 두 부모중 작은 값을 가지는 부모로 합쳐준다.
const unionParent = (parent, x, y) => {
   const n1 = getParent(parent,x);
   const n2 = getParent(parent,y);
   if(n1<n2) return parent[n2] = n1;
   else return parent[n1] = n2;
}

// 두 섬의 부모를 찾고, 부모가 같으면 true, 다르면 false return
 const findParent = (parent, x, y) => {
   const n1 = getParent(parent,x);
   const n2 = getParent(parent,y);
   if(n1===n2) return true;
   else return false;
}

上記で実現したUnion-Findアルゴリズムを用いて,現在ではクルーズアルゴリズムを実現できるようになった.

for(const cost of costs){
  // 만약 두 섬의 부모가 다르면, 즉 사이클이 형성되지 않은 상태라면
  if(!findParent(parent,cost[0],cost[1])){
    answer += cost[2];	// 정답에 해당 가중치를 더해준다 (오름차순으로 정렬해서 작은값 선택 가능)
    unionParent(parent,cost[0],cost[1]);  // 이제 두 섬은 연결되었으니 합쳐준다
  }
}

正しいコード

function solution(n, costs) {
    let answer = 0;
    const parent = [];
    for(let i=0; i<n; i++) parent.push(i);
    
    costs.sort((a,b)=>a[2]-b[2]);
     
    const getParent = (parent, x) => {
        if(parent[x] === x) return x;
        return parent[x] = getParent(parent,parent[x]);
    }
    
    const unionParent = (parent, x, y) => {
        const n1 = getParent(parent,x);
        const n2 = getParent(parent,y);
        if(n1<n2) return parent[n2] = n1;
        else return parent[n1] = n2;
    }
    
    const findParent = (parent, x, y) => {
        const n1 = getParent(parent,x);
        const n2 = getParent(parent,y);
        if(n1===n2) return true;
        else return false;
    }
    
    for(const cost of costs){
        if(!findParent(parent,cost[0],cost[1])){
            answer += cost[2];
            unionParent(parent,cost[0],cost[1]);
        }
    }
    return answer;
}

参考資料
参考資料
参考運賃