Minimum Spanning Tree (最小生成樹)
- 所有節點都要連通,且邊的權重總和最低。
- 邊的數量為節點數-1
Kruskal's Algorithms
步驟:
- 將所有邊依照權重(weight)做排序
- 將邊依序由權重小至大加入到圖中,若加入的邊產生迴圈(cycle)則丟棄。
- 重複步驟 2,直到圖中的邊數為節點數-1
檢查是否產生迴圈
可以使用Union-Find Algorithm。所有節點用一個 subset 來紀錄節點是否有共同的 parent,若有共同 parent 代表兩個節點是同一個集合(連通的)。
const find = (subset, i) => {
if (subset[i] === -1) {
return i;
}
return find(subset, subset[i]);
};
const union = (subset, x, y) => {
let xset = find(subset, x);
let yset = find(subset, y);
subset[xset] = yset;
};
let subset = Array(points.length).fill(-1);
for (let i = 0, numOfEdge = 0; ; i++) {
const { weight, src, dist } = edges[i];
let x = find(subset, src);
let y = find(subset, dist);
//...
}
subset 每個 index 表示節點的號碼,初始值設為-1,搜尋到-1 就會結束 find(),並回傳節點 index。 將邊(src, dist)的 src, dist 節點分別帶入 find(),若 x 與 y 相同表示 x 與 y 是同一個集合(產生迴圈)。 若產生迴圈則捨棄這個邊,若沒有產生迴圈則執行 union()將邊加入圖中,並更新 subset。
JavaScript Implementation:
const find = (subset, i) => {
if (subset[i] === -1) {
return i;
}
return find(subset, subset[i]);
};
const union = (subset, x, y) => {
let xset = find(subset, x);
let yset = find(subset, y);
subset[xset] = yset;
};
/**
* @param {number[][]} points
* @return {number}
*/
var kruskal = function (points) {
if (points.length <= 1) return 0;
let edges = []; // [{weight: 1, src: 0, dist: 1}, ....]
points.map((point1, src) => {
points.map((point2, dist) => {
let manhattan = Math.abs(point1[0] - point2[0]) + Math.abs(point1[1] - point2[1]);
if (src !== dist) edges.push({ weight: manhattan, src: src, dist: dist });
});
});
edges.sort((e1, e2) => e1.weight - e2.weight); //sorted edges.
console.log(edges);
let subset = Array(points.length).fill(-1);
let cost = 0;
for (let i = 0, numOfEdge = 0; ; i++) {
const { weight, src, dist } = edges[i];
let x = find(subset, src);
let y = find(subset, dist);
if (x === y) {
console.log("Add Edge:", src, " --> ", dist, "(has cycle)");
}
if (x !== y) {
console.log("Add Edge:", src, " --> ", dist);
union(subset, x, y);
cost += weight;
numOfEdge += 1;
console.log("subset:", subset);
}
if (numOfEdge >= points.length - 1) break; // if there are v -1 edges ---> fininsh.
}
return cost;
};