Problem: algorytm Kruskala znajdowania optymalnego drzewa rozpinającego grafu









Struktury danych:

K - kolejka priorytetowa krawędzi
T - zbiór krawędzi do którego będą wstawiane krawędzie
obliczanego drzewa rozpinającego
P - podział zbioru wierzchołków








Algorytm Kruskala:

1. K = kolejka priorytetowa wszystkich krawędzi grafu;
2. P = podział początkowy zbioru wszystkich wierzchołków grafu;
3. T = pusty zbiór krawędzi;

4. dopóki w podziale P jest więcej niż jeden zbiór wykonuj

4.1 e = minimalna krawędź kolejki K;
4.2 x, y = końce krawędzi e;
4.3 wyrzuć minimalną krawędź z kolejki K;
4.4 znajdź w podziale P zbiór X do którego należy wierzchołek x;
4.5 znajdź w podziale P zbiór Y do którego należy wierzchołek y;
4.6 jeżeli X<>Y to
4.6.1 wstaw krawędź e do zbioru T;
4.6.2 wyrzuć z podziału P zbiory X,Y i wstaw do P
zbiór X ∪ Y (union(X,Y)) ;

{ T jest zbiorem krawędzi optymalnego drzewa rozpinającego }



Przykład:
Początkowy podział P = { {1},{2}, … , {7} }
K = (2,3),(3,4),(4,6),(3,6),(3,5),(1,3),(2,5),(5,7),(1,4),(6,7),(5,6),(1,2)

krawędź wstawiana
x y do T P

2 3 (2,3) {{1},{2,3},{4},{5},{6},{7}}
3 4 (3,4) {{1},{2,3,4},{5},{6},{7}}
4 6 (4,6) {{1},{2,3,4,6},{5},{7}}
3 6 - {{1},{2,3,4,6},{5},{7}}
3 5 (3,5) {{1},{2,3,4,5,6},{7}}
1 3 (1,3) {{1,2,3,4,5,6},{7}}
2 5 - {{1,2,3,4,5,6},{7}}
5 7 (5,7) {{1,2,3,4,5,6,7}}






Optymalne drzewo rozpinające:

1

2

3

4

5

6

7

1

2

3

4

6

7

8

9

10

11

12

1

2

3

4

5

6

7

---