---
tags: 演算法, LeetCode
disqus: HackMD
---
# 最小生成樹（minimum spanning tree，MST）
## 介紹
最小生成樹（Minimum Spanning Tree，MST）是指在一個帶權無向圖中，找到一棵包含所有節點，權值最小的樹。其中，權值是指樹中所有邊權重的總和。
那甚麼是有向圖甚麼是無向圖?
* 無向圖
(圖片取自於[wiki](https://zh.wikipedia.org/zh-tw/%E5%9B%BE_(%E6%95%B0%E5%AD%A6)#%E5%9B%BE))
無向圖是指其中的邊沒有方向，也就是連接兩個節點的邊沒有特定的起點和終點。
以生活例子舉例，社交軟體中用戶之間的關係就可以用無向圖表示，**用戶之間的好友關係**，每個用戶可以視為一個節點，而好友關係可以視為無向邊。
* 有向圖
(圖片取自於[wiki](https://zh.wikipedia.org/zh-tw/%E5%9B%BE_(%E6%95%B0%E5%AD%A6)#%E5%9B%BE))
有向圖是指其中的邊有方向，也就是從一個節點到另一個節點的邊有明確的起點和終點。一個經典的例子是在網絡傳輸中，**路由器之間的連接**可以用有向圖來表示，每個路由器可以視為一個節點，而連接可以視為有向邊，表示數據傳輸的方向。
最小生成樹在很多場合都有應用，比如連通無向圖的最小成本設計、最短路徑問題等。下面介紹幾種常見的求最小生成樹的算法：
1. Kruskal算法
`Kruskal`算法是一種貪心算法，通過按照邊權值從小到大的順序加入圖中的邊，同時排除會形成環的邊，最終得到最小生成樹。
1. Prim算法
`Prim`算法也是一種貪心算法，通過按照節點與樹的距離從小到大的順序加入樹中，同時保證加入的邊不會形成環，最終得到最小生成樹。
1. Boruvka算法
`Boruvka`算法是一種基於連通性的貪心算法，通過不斷找到每個連通分量中權值最小的邊加入生成樹中，直到整個圖連通為止。
## 複雜度
`E`是邊的數量，`V`是頂點的數量
| 演算法 | 時間複雜度 | 空間複雜度 |
| -------- | -------- | -------- |
| Prim's Algorithm | $O(E log V)$ or $O(V^2)$ for adjacency matrix | $O(V)$ |
| Kruskal's Algorithm | $O(E log E)$ or $O(E log V)$ | $O(E+V)$ |
| Boruvka's Algorithm | $O(E log V)$ | $O(E+V)$ |
## Kruskal算法
`Kruskal`算法中文稱作克魯斯克爾演算法，是一種貪心算法，它將所有邊按權重排序，然後遍歷每一條邊，如果加入這條邊不會形成環路，就把它加入生成樹中，直到生成樹中包含所有節點為止。
(圖片取自於[visualgo](https://visualgo.net/en/mst))
### 程式實現
```javascript=
// 定義一個邊的類別
class Edge {
constructor(from, to, weight) {
this.from = from;
this.to = to;
this.weight = weight;
}
}
// 定義一個圖的類別
class Graph {
constructor(numVertices) {
this.numVertices = numVertices;
this.edges = [];
}
// 添加一個邊到圖中
addEdge(edge) {
this.edges.push(edge);
}
// 找到最小生成樹
findMinimumSpanningTree() {
// 將邊按照權重排序
this.edges.sort((a, b) => a.weight - b.weight);
const parent = new Array(this.numVertices);
for (let i = 0; i < this.numVertices; i++) {
parent[i] = i;
}
const result = [];
let edgeCount = 0;
let i = 0;
while (edgeCount < this.numVertices - 1) {
const edge = this.edges[i];
const root1 = this.find(parent, edge.from);
const root2 = this.find(parent, edge.to);
if (root1 !== root2) {
result.push(edge);
parent[root1] = root2;
edgeCount++;
}
i++;
}
return result;
}
// 找到一個節點的根節點
find(parent, node) {
if (parent[node] !== node) {
parent[node] = this.find(parent, parent[node]);
}
return parent[node];
}
}
// 創建一個有6個節點的圖
const g = new Graph(6);
// 添加所有邊到圖中
g.addEdge(new Edge(0, 1, 6));
g.addEdge(new Edge(0, 2, 1));
g.addEdge(new Edge(0, 3, 5));
g.addEdge(new Edge(1, 4, 3));
g.addEdge(new Edge(2, 4, 4));
g.addEdge(new Edge(2, 3, 5));
g.addEdge(new Edge(2, 5, 2));
g.addEdge(new Edge(3, 5, 5));
g.addEdge(new Edge(4, 5, 6));
// 找到最小生成樹
const minimumSpanningTree = g.findMinimumSpanningTree();
console.log(minimumSpanningTree);
```
### 解釋
在這段程式碼中，`Kruskal's Algorithm`被用來找出一個圖中的最小生成樹。該算法的主要步驟如下：
1. **定義數據結構**： 首先，我們定義了兩個類別：`Edge`（表示圖中的邊）和 `Graph`（表示圖）。Edge 有起點（from）、終點（to）和權重（weight）三個屬性。`Graph` 則包含節點數量（numVertices）和邊的集合（edges）兩個屬性。
1. **添加邊**： 在 `Graph` 中有一個方法叫做 `addEdge`，用來將邊添加到圖中的邊的集合裡。
1. **找出最小生成樹**： `Graph` 也有一個方法叫做 `findMinimumSpanningTree`，它的目的是找出圖中的最小生成樹。首先，所有的邊會按照權重大小排序。然後，為每個節點創建一個 `parent` 陣列，初始狀態下每個節點的 `parent` 都是自己。
1. **連接邊與節點**： 然後，進行一個迴圈，直到生成樹中的邊數量為節點數量減一。在每次迴圈中，選取下一個權重最小的邊，並找出該邊的兩個節點的根節點。如果這兩個根節點不相同，就將該邊加入到生成樹中，並將其中一個節點的根節點更新為另一個節點，增加已經連接的邊的數量。
1. **確認節點的根節點**： 此外，還有一個方法叫做 `find`，它用於找出一個節點的根節點。如果一個節點的 `parent` 不是它自己，那麼就更新它的 `parent` 為其 `parent` 的根節點，並最終返回它的根節點。
1. **建立圖並找出最小生成樹**： 在程式碼的最後部分，我們創建了一個包含6個節點的圖，添加了所有的邊，並找出了該圖的最小生成樹。最小生成樹的結果會被輸出到控制台上。
透過以上的步驟，我們可以找出一個圖中的最小生成樹。
## Prim算法
`Prim` 演算法又稱作普林演算法是一種貪心算法，它以一個節點為起始點，每次找到一個到已經選擇的節點集合距離最小的節點加入集合中，重複此過程直到所有節點都被選擇為止。
建構要點:
* 不管以哪個節點為起始點會得到同樣結果
* 需追蹤那些節點已訪問過
* 紀錄哪接 `edges` 屬於 `MST`
* `MST`是樹，所以節點不能有`cyclic`
(圖片取自於[visualgo](https://visualgo.net/en/mst))
### 程式實現
```javascript=
class PriorityQueue {
constructor() {
this.queue = [];
}
enqueue(element, priority) {
this.queue.push({element, priority});
this.queue.sort((a, b) => a.priority - b.priority);
}
dequeue() {
return this.queue.shift().element;
}
isEmpty() {
return this.queue.length === 0;
}
}
class Graph {
constructor() {
this.nodes = [];
this.edges = {};
}
addNode(node) {
this.nodes.push(node);
this.edges[node] = {};
}
addEdge(node1, node2, weight) {
this.edges[node1][node2] = weight;
this.edges[node2][node1] = weight;
}
getNeighbors(node) {
return Object.keys(this.edges[node]);
}
getEdgeWeight(node1, node2) {
return this.edges[node1][node2];
}
prim(startNode) {
const visited = {};
const pq = new PriorityQueue();
let totalWeight = 0;
let currentNode = startNode;
while (currentNode) {
visited[currentNode] = true;
const neighbors = this.getNeighbors(currentNode);
neighbors.forEach(neighbor => {
if (!visited[neighbor]) {
const weight = this.getEdgeWeight(currentNode, neighbor);
pq.enqueue({node: neighbor, weight}, weight);
}
});
const nextNode = pq.isEmpty() ? null : pq.dequeue().node;
if (nextNode) {
totalWeight += this.getEdgeWeight(currentNode, nextNode);
}
currentNode = nextNode;
}
return totalWeight;
}
}
const graph = new Graph();
graph.addNode('A');
graph.addNode('B');
graph.addNode('C');
graph.addNode('D');
graph.addNode('E');
graph.addEdge('A', 'B', 2);
graph.addEdge('A', 'C', 3);
graph.addEdge('B', 'C', 1);
graph.addEdge('B', 'D', 1);
graph.addEdge('C', 'D', 4);
graph.addEdge('C', 'E', 3);
graph.addEdge('D', 'E', 2);
const totalWeight = graph.prim('A');
console.log(totalWeight); // Output: 6
```
### 解釋
這段程式碼主要包含兩個部分：`PriorityQueue` 類別和 `Graph` 類別。它們共同用於實現一種稱為 `Prim's` 算法的計算機算法。
#### PriorityQueue（優先隊列）類別：
這是一個數據結構，它存儲元素並按照給定的優先級對這些元素進行排序。在這裡，優先級越高（數值越小），元素在隊列中的位置越前。
* `enqueue(element, priority)` 是用來將一個元素添加到隊列中，並按照優先級重新排序隊列。
* `dequeue()` 是用來移除並返回隊列中優先級最高（值最小）的元素。
* `isEmpty()` 是用來檢查隊列是否為空。
#### Graph（圖）類別：
這個類別描述了一種數學結構，稱為「圖」，包含了節點（nodes）和邊（edges）。
* `addNode(node)` 用來添加一個節點到圖中。
* `addEdge(node1, node2, weight)` 用來添加一條連接兩個節點的邊，並賦予該邊一個權重（通常代表兩個節點之間的某種距離或成本）。
* `getNeighbors(node)` 返回一個節點的所有鄰居節點。
* `getEdgeWeight(node1, node2)` 返回連接兩個節點的邊的權重。
#### Prim's 算法（prim 函數）：
該函數用於在一個加權無向圖中找到一棵包含所有節點且總邊權最小的生成樹（minimum spanning tree）。
這個算法的操作方式如下：
1. **選擇起點**： 首先，從圖中的任一節點開始。一開始，這個節點被標記為已訪問。
1. **尋找最小邊**： 然後，將該節點的所有未訪問的鄰居節點放入一個優先隊列中，這個隊列會按照與當前節點相連接的邊的權重來排序。
1. **擴展樹**： 從這個優先隊列中選擇一個權重最小的節點，標記為已訪問，然後將該節點的所有未訪問的鄰居節點也加入到優先隊列中。
1. **重複步驟**： 這個過程會一直重複下去，直到所有的節點都被訪問過。在每一步中，都會選擇與已訪問節點之間權重最小的未訪問節點來擴展這棵樹。
1. **結束**： 當所有的節點都被訪問過，算法結束。此時，生成的樹就是我們要找的最小生成樹。
最終，算法會返回這棵最小生成樹的總邊權，也就是所有邊的權重之和。
Sign in with Wallet
Connect another wallet