kruskala

Algorytm Kruskala

Idea algorytmu Kruskala jest następująca:

Tworzymy pusty zbiór krawędzi T oraz listę L wszystkich krawędzi grafu uporządkowaną według rosnących wag.

Dopóki w T nie mamy wszystkich wierzchołków grafu, wybieramy z listy L krawędź i, jeśli nie tworzy ona cyklu z krawędziami już obecnymi w T, dodajemy ją do zbioru T.

Gdy algorytm zakończy pracę, w T będzie minimalne drzewo rozpinające.

W poniższej tabelce podajemy przykład znajdowania minimalnego drzewa rozpinającego za pomocą algorytmu Kruskala.

L

4-6:1

4- 5:2 2-7:3 0-6:3 2-4:4

0- 1:5

2- 6:5

1- 5:6

5- 6:6 1-7:7 1-4:8

3- 6:8

0- 3:9

1- 2:9

2- 3:9

6- 7:9

Oto nasz graf ważony, dla którego mamy znaleźć minimalne drzewo rozpinające. Tworzymy pusty zbiór krawędzi T oraz uporządkowaną wg rosnących wag listę L krawędzi grafu

4-6:1

4-5:2

4-6:1

4-5:2

2-7:3

0-6:3

T

4-6:1

4-5:2

2-7:3

0-6:3

2-4:4

T

T

T

4-6:1

T

T

4-6:1

4-5:2

2-7:3

T

4-6:1

4-5:2

2-7:3

0-6:3

2-4:4

0-1:5

4-6:1

4-5:2

2-7:3

0-6:3

2-4:4

0-1:5

L

4-6:1

4- 5:2 2-7:3 0-6:3 2-4:4

0- 1:5

2- 6:5

1- 5:6

5- 6:6 1-7:7 1-4:8

3- 6:8

0- 3:9

1- 2:9

2- 3:9

6- 7:9

L

4- 5:2 2-7:3 0-6:3 2-4:4

0- 1:5

2- 6:5

1- 5:6

5- 6:6 1-7:7 1-4:8

3- 6:8

0- 3:9

1- 2:9

2- 3:9

6- 7:9

L

2-7:3

0-6:3

2-4:4

0- 1:5

2- 6:5

1- 5:6

5- 6:6 1-7:7 1-4:8

3- 6:8

0- 3:9

1- 2:9

2- 3:9

6- 7:9

L

0-6:3

2-4:4

0- 1:5

2- 6:5

1- 5:6

5- 6:6 1-7:7 1-4:8

3- 6:8

0- 3:9

1- 2:9

2- 3:9

6- 7:9

L

2-4:4

0- 1:5

2- 6:5

1- 5:6

5- 6:6 1-7:7 1-4:8

3- 6:8

0- 3:9

1- 2:9

2- 3:9

6- 7:9

L

0- 1:5

2- 6:5

1- 5:6

5- 6:6 1-7:7 1-4:8

3- 6:8

0- 3:9

1- 2:9

2- 3:9

6- 7:9

L

2- 6:5 1-5:6

5- 6:6 1-7:7 1-4:8

3- 6:8

0- 3:9

1- 2:9

2- 3:9

6- 7:9

T		L
4-6:1		3-6:8
4-5:2		0-3:9
2-7:3		1-2:9
0-6:3		2-3:9
2-4:4		6-7:9
0-1:5
3-6:8

Pobieramy z L krawędź 3-6:8 i dołączamy do T. Suma wag = 1 + 2 + 3 + 3 + 4 + 5 + 8 = 26

T		L
4-6:1		0-3:9
4-5:2		1-2:9
2-7:3		2-3:9
0-6:3		6-7:9
2-4:4
0-1:5
3-6:8

Pobieramy z listy L krawędź 4-6:1 i dodajemy ją do zbioru T. Krawędź ta będzie należała do minimalnego drzewa rozpinającego.

Suma wag = 1

Pobieramy z L kolejną krawędź 4-5:2 i dodajemy ją do zbioru T. Suma wag = 1 +2 = 3

Pobieramy z L krawędź 2-7:3 i dołączamy do T. Suma wag = 1 + 2 + 3 = 6

Pobieramy z L krawędź 0-6:3 i dołączamy do T. Suma wag = 1 + 2 + 3 + 3 = 9

Pobieramy z L krawędź 2-4:4 i dołączamy do T. Suma wag = 1 + 2 + 3 + 3 + 4 = 13

Pobieramy z L krawędź 0-1:5 i dołączamy do T. Suma wag = 1 + 2 + 3 + 3 + 4 + 5 = 18

Pobieramy z L krawędzie: 2-6:5, 1-5:6, 5-6:6, 1-7:7 i 1-4:8, lecz nie dodajemy ich do T, ponieważ utworzyłyby one cykle z krawędziami już obecnymi w T.

Zbiór T obejmuje wszystkie wierzchołki grafu, otrzymaliśmy minimalne drzewo rozpinające o sumie wag krawędzi równej 26.