---
# System prepended metadata

title: Kruskal演算法
tags: [演算法]

---

---
title: Kruskal演算法
tags:  演算法
description: 簡述使用Kruskal演算法獲得最小生成樹
---
# Kruskal演算法

Kruskal演算法是一種可以求得最小生成樹的方法。

邏輯上是一種greedy式的求法，從權重最小的邊開始連線，並在途中避免環的產生，最後出來的結果就會是最小生成樹。

## 作法

1. 首先先將所有邊按照權重排序
2. 依序將邊連接起來，若是連接後會形成環則回溯並拋棄這條邊，並往下一條繼續檢查
3. 將所有邊檢查依序檢查完畢後，所有連接的樹理論上為最小生成樹

## 範例

我們以這張圖作為範例

![1 (1)](https://hackmd.io/_uploads/H10QWXlhR.png)

首先我們將所有邊以點對的形式，依權重大小排序

```
3-5 1
1-3 2
4-5 2
1-7 3
2-4 3
6-7 3
5-6 4
1-2 5
2-3 7
1-6 10
```

接著按照權重的排序，由小到大將邊連起來

![1](https://hackmd.io/_uploads/ry8LwXghR.png)

接著可以將邊標記為確定使用

```
3-5 1 V
1-3 2
4-5 2
1-7 3
2-4 3
6-7 3
5-6 4
1-2 5
2-3 7
1-6 10
```

![1 (3)](https://hackmd.io/_uploads/Sy0TPQghR.png)

繼續重複前一個操作，以下就只放圖省略紀錄

```
3-5 1 V
1-3 2 V
4-5 2
1-7 3
2-4 3
6-7 3
5-6 4
1-2 5
2-3 7
1-6 10
```

![1 (4)](https://hackmd.io/_uploads/ryYAD7x20.png)

![1 (5)](https://hackmd.io/_uploads/S1zyuQxnC.png)

![1 (7)](https://hackmd.io/_uploads/rkPZdme30.png)

![1 (8)](https://hackmd.io/_uploads/HJTWOQenA.png)

連到這裡之後我們會發現
再往下的`5-6 4`連接之後會形成環
那此時我們就不要將這條邊連起來，而紀錄上則標記為不使用

```
3-5 1 V
1-3 2 V
4-5 2 V
1-7 3 V
2-4 3 V
6-7 3 V
5-6 4 X
1-2 5
2-3 7
1-6 10
```

以此類推，往下的都沒辦法使用了，將可用的邊連之後，所產生的圖即為最小生成樹了。

## 練習

## reference

> [link text](https:// "title")
> [name=Miyago]