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

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

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

## 作法

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

## 範例

我們以這張圖作為範例


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

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

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


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

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


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

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





連到這裡之後我們會發現
再往下的`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]