C# Union-Find木の実装と応用例をやったので、今回はJavaScriptで同じようなことをやってみます。
まずはHTML部分を示します。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
<!DOCTYPE html> <html lang="ja"> <head> <meta charset="UTF-8"> <title>最小全域木を求める</title> <meta name = "viewport" content = "width=device-width, initial-scale = 1.0"> <link rel = "stylesheet" href = "./style.css" type = "text/css" media = "all"> </head> <body> 頂点数：<input type="number" id = "vertex-count"> 二つの頂点番号とコスト（入力例 0 1 10）：<br> <textarea id="edges" rows="5" cols="25"></textarea> <button id = "calc">計算</button> <button id = "clear">クリア</button> <textarea id="result" rows="15" cols="25"></textarea><br> <script src= "./index.js"></script> </body> </html> |
style.css
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
#vertex-count, #edges, #result { display: block; } #edges { margin-bottom: 10px; } #result { margin-top: 30px; } #calc, #clear { width: 100px; height: 40px; } |
index.js
どの頂点間をつなぐ辺なのか？そのコストをEdgeクラスを定義して管理します。
|
1 2 3 4 5 6 7 |
class Edge { constructor(vertexNum1, vertexNum2, cost){ this.VertexNum1 = vertexNum1; this.VertexNum2 = vertexNum2; this.Cost = cost; } } |
グローバル変数と定数を示します。
index.js
|
1 2 3 4 5 |
const $vertexCount = document.getElementById('vertex-count'); const $edges = document.getElementById('edges'); const $calc = document.getElementById('calc'); const $result = document.getElementById('result'); const $clear = document.getElementById('clear'); |
find関数はUnion-Find木で使う関数です。iは要素の番号、arr[i]は各要素の親です。
|
1 2 3 4 5 6 7 8 |
function find(i, arr){ if (i == arr[i]) return i; else { arr[i] = find(arr[i], arr); return arr[i]; } } |
ページが読み込まれたら初期値をセットします。頂点は6つあり、辺の情報として0番と1番をつなぐコストは9、2番と5番をつなぐコストは17…というふうに指定します。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
window.onload = () => { // 初期値をセット $vertexCount.value = '6'; $edges.value = `0 1 9 2 5 17 1 4 49 0 5 19 1 5 9 1 3 7 3 5 40 1 2 35 2 3 46 0 2 39 2 4 10`; } |
イベントリスナを追加します。計算ボタンがクリックされたらUnion-Find木とクラスカルのアルゴリズムで最小全域木を求めます。クリアボタンがクリックされたらテキストエリアに入力されている文字列をすべて消去します。
|
1 2 3 4 5 6 7 8 |
$calc?.addEventListener('click', () => { calc(); }); $clear?.addEventListener('click', () => { $vertexCount.value = ''; $edges.value = ''; $result.value = ''; }); |
calc関数は最小全域木を求める処理をおこないます。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 |
function calc(){ const vertexCount = Number($vertexCount.value); // 頂点の数だけ配列を用意する // arrは[0, 1, 2, 3...]、 ranksは[1, 1, 1, 1...] で初期化する const arr = []; const ranks = []; for(let i = 0; i < vertexCount; i++){ arr.push(i); ranks.push(1); } // テキストエリアの文字列からEdgeオブジェクトを生成して配列に格納する const edgeTexts = $edges.value.split('\n'); let edges = []; edgeTexts.forEach(text => { if(text != ''){ const arr2 = text.split(' '); edges.push(new Edge(Number(arr2[0]), Number(arr2[1]), Number(arr2[2]))); } }); // コストが低い順にソートする edges = edges.sort((edge1, edge2) => edge1.Cost - edge2.Cost); let useEdges = []; edges.forEach(edge => { const rootA = find(edge.VertexNum1, arr); const rootB = find(edge.VertexNum2, arr); // rootB != rootAなら閉路は形成されないのでグラフに追加する if (rootB != rootA) { if (ranks[rootA] == ranks[rootB]){ arr[rootB] = rootA; ranks[rootA]++; } else if (ranks[rootA] > ranks[rootB]) arr[rootB] = rootA; else if (ranks[rootA] < ranks[rootB]) arr[rootA] = rootB; // グラフに追加した辺をリストに格納しておく useEdges.push(edge); } }); // 連結判定（ルートが1つだけか確認） const root0 = find(0, arr); let ok = true; for (let i = 0; i < arr.length; i++){ // 各頂点のルートを求めてがroot0以外のものがあればすべての頂点が連結していないことになる if(root0 != find(i, arr)){ ok = false; break; } } if (ok){ // コストと使用する辺を出力する let text = ''; let cost = 0; for(let i=0; i<useEdges.length; i++){ cost += useEdges[i].Cost; } // コストと使用する辺を出力する text += '最小全域木のコストは' + cost + '\n'; text += '使用する辺は' + '\n'; useEdges.forEach(edge => { text += `${edge.VertexNum1} - ${edge.VertexNum2}\n`; }); $result.value = text; } else { // ok == false ならすべての頂点が連結していないので最小全域木は存在しない $result.value = '最小全域木は存在しません'; } } |
