Minimalne drzewo rozpinające - algorytmy Prima i Kruskala

Wprowadzenie

Minimalne drzewo rozpinające (ang. Minimum Spanning Tree, MST) to podgraf spójnego grafu ważonego, który: - Jest drzewem (spójny i acykliczny) - Rozpina cały graf (zawiera wszystkie wierzchołki) - Ma minimalną sumę wag krawędzi

MST jest fundamentalnym problemem w teorii grafów z licznymi zastosowaniami praktycznymi.

Zastosowania: - Projektowanie sieci (telekomunikacyjne, elektryczne, wodociągowe) - Minimalizacja kosztów połączeń między miastami - Analiza skupień (clustering w machine learning) - Aproksymacja problemu komiwojażera (TSP) - Optymalizacja tras dostaw - Projektowanie układów scalonych (minimalizacja przewodów)

Własność: Graf z n wierzchołkami ma drzewo rozpinające z dokładnie n-1 krawędziami.

Problem minimalnego drzewa rozpinającego

Definicja formalna

Dany jest graf nieskierowany, spójny i ważony G = (V, E) z wagami w: E → ℝ.

Drzewo rozpinające T = (V, E') to podgraf, gdzie: - E' ⊆ E - |E'| = |V| - 1 - Graf T jest spójny (łączy wszystkie wierzchołki)

Minimalne drzewo rozpinające to drzewo rozpinające o minimalnej sumie wag:

waga(T) = Σ w(e) → minimum
         e∈E'

Wizualizacja

Graf wejściowy:
        1
    A ---- B
    |    / |
   4|  2/  |3
    | /    |
    C ---- D
        1

Wszystkie możliwe drzewa rozpinające:

Drzewo 1: A-B, B-C, C-D    Waga = 1+2+1 = 4  ← MST!
Drzewo 2: A-B, B-D, C-D    Waga = 1+3+1 = 5
Drzewo 3: A-C, B-C, C-D    Waga = 4+2+1 = 7
Drzewo 4: A-B, A-C, B-D    Waga = 1+4+3 = 8
... (inne kombinacje)

MST zawiera krawędzie: {A-B: 1, B-C: 2, C-D: 1}

Uwaga: MST nie musi być unikalne (jeśli są krawędzie o tej samej wadze).

Własności MST - twierdzenia

Twierdzenie 1: Własność cięcia (Cut Property)

Cięcie grafu to podział wierzchołków na dwa rozłączne zbiory S i V-S.

Twierdzenie: Dla dowolnego cięcia (S, V-S), najlżejsza krawędź przecinająca cięcie (łącząca S z V-S) należy do pewnego MST.

Przykład:
        1
    A ---- B
    |      |
   4|      |3
    |      |
    C ---- D
        5

Cięcie: S = {A, C}, V-S = {B, D}
Krawędzie przecinające: A-B (1), C-D (5)
Najlżejsza: A-B (1) → musi być w MST

Algorytm Prima wykorzystuje tę własność.

Twierdzenie 2: Własność cyklu (Cycle Property)

Twierdzenie: Dla dowolnego cyklu w grafie, najcięższa krawędź w cyklu nie należy do żadnego MST.

Przykład:
    A ---- B
    |      |
   2|      |3
    |      |
    C ---- D
        5    (najcięższa w cyklu A-B-D-C-A)

Krawędź C-D (5) nie może być w MST, bo tworzy cykl
i jest najcięższa → usuwamy ją

Algorytm Kruskala wykorzystuje tę własność (unika dodawania krawędzi tworzących cykl).

Algorytm Prima - "rosnące drzewo"

Idea algorytmu

Algorytm Prima działa podobnie do algorytmu Dijkstry, ale zamiast szukać najkrótszej ścieżki, buduje MST:

Zaczynaj od dowolnego wierzchołka
W każdym kroku dodaj najlżejszą krawędź łączącą drzewo z wierzchołkiem spoza drzewa
Kontynuuj, aż wszystkie wierzchołki będą w drzewie

Strategia zachłanna: Zawsze wybieramy najtańsze połączenie z obecnym drzewem.

Pseudokod algorytmu Prima

Prim(graf G, wierzchołek start):
    1. Inicjalizacja:
        - T = {start}           // Drzewo MST (wierzchołki)
        - E_T = ∅               // Krawędzie MST
        - PQ = kolejka priorytetowa

    2. Dla każdego sąsiada v wierzchołka start:
        - Dodaj (waga, start, v) do PQ

    3. Dopóki |T| < |V|:
        a. (waga, u, v) = PQ.extract_min()

        b. Jeśli v już w T:
            - continue  // Pomiń

        c. Dodaj v do T
        d. Dodaj krawędź (u, v) do E_T

        e. Dla każdego sąsiada w wierzchołka v:
            - Jeśli w nie w T:
                - Dodaj (waga(v,w), v, w) do PQ

    4. Zwróć (T, E_T)

Złożoność: - Z binary heap: O(E log V) - Z Fibonacci heap: O(E + V log V)

Implementacja algorytmu Prima

Podstawowa implementacja

Wyjście:

=== Algorytm Prima ===

Krawędzie MST:
  A - B: 1
  B - C: 2
  C - D: 1

Całkowita waga MST: 4

Prim krok po kroku - wizualizacja

Przykładowe wyjście:

=== Prim krok po kroku ===

Start: A
Drzewo: {A}

Kolejka po inicjalizacji: [(1, 'A', 'B'), (4, 'A', 'C')]

Krok 1: Dodaję krawędź A-B (waga: 1)
  Drzewo: {'A', 'B'}
  Dodaję do kolejki: [('B', 'C', 2), ('B', 'D', 3)]
  Kolejka: [(2, 'B', 'C'), (3, 'B', 'D'), (4, 'A', 'C')]

Krok 2: Dodaję krawędź B-C (waga: 2)
  Drzewo: {'A', 'B', 'C'}
  Dodaję do kolejki: [('C', 'D', 1)]
  Kolejka: [(1, 'C', 'D'), (3, 'B', 'D'), (4, 'A', 'C')]

Krok 3: Dodaję krawędź C-D (waga: 1)
  Drzewo: {'A', 'B', 'C', 'D'}
  Kolejka: [(3, 'B', 'D'), (4, 'A', 'C')]

Algorytm Kruskala - "sortowanie krawędzi"

Idea algorytmu

Algorytm Kruskala działa inaczej niż Prim - zamiast budować jedno drzewo, łączy lasy:

Sortuj wszystkie krawędzie rosnąco według wag
Przeglądaj krawędzie w kolejności:
Jeśli krawędź nie tworzy cyklu, dodaj ją do MST
Jeśli tworzy cykl, pomiń
Zakończ po dodaniu n-1 krawędzi

Kluczowe pytanie: Jak sprawdzić czy krawędź tworzy cykl? Odpowiedź: Struktura Union-Find (Disjoint Set Union)!

Pseudokod algorytmu Kruskala

Kruskal(graf G):
    1. Posortuj wszystkie krawędzie E rosnąco według wag

    2. Utwórz strukturę Union-Find dla wszystkich wierzchołków
       (każdy wierzchołek w osobnym zbiorze)

    3. E_T = ∅  // Krawędzie MST

    4. Dla każdej krawędzi (u, v, waga) w posortowanej kolejności:
        a. Jeśli Find(u) ≠ Find(v):  // Różne zbiory (nie ma cyklu)
            i.  Dodaj (u, v) do E_T
            ii. Union(u, v)  // Połącz zbiory

        b. Jeśli |E_T| == |V| - 1:
            - Przerwij (MST kompletne)

    5. Zwróć E_T

Złożoność: - Sortowanie: O(E log E) - Operacje Union-Find: O(E α(V)) gdzie α to odwrotna funkcja Ackermanna (≈ stała) - Całkowita: O(E log E) = O(E log V)

Struktura Union-Find (Disjoint Set Union)

Idea

Union-Find to struktura danych utrzymująca rozłączne zbiory z operacjami: - Find(x) - znajdź reprezentanta (root) zbioru zawierającego x - Union(x, y) - połącz zbiory zawierające x i y

Zastosowanie w Kruskalu: - Każdy wierzchołek zaczyna w osobnym zbiorze - Find(u) == Find(v) → u i v są już połączone → dodanie krawędzi tworzy cykl - Union(u, v) → połącz składowe zawierające u i v

Implementacja Union-Find

Wyjście:

=== Union-Find Test ===

A i B połączone? False

Po union(A, B):
A i B połączone? True

Po union(C, D) i union(B, C):
A i D połączone? True
A i E połączone? False

Implementacja algorytmu Kruskala

Wyjście:

=== Algorytm Kruskala ===

Krawędzie MST:
  A - B: 1
  C - D: 1
  B - C: 2

Całkowita waga MST: 4

Kruskal krok po kroku - wizualizacja

Przykładowe wyjście:

=== Kruskal krok po kroku ===

Krawędzie posortowane według wag:
  A-B: 1
  C-D: 1
  B-C: 2
  B-D: 3
  A-C: 4

Krok 1: Sprawdzam krawędź A-B (waga: 1)
  ✓ Dodaję do MST (nie tworzy cyklu)
  MST: [('A', 'B', 1)]
  Komponenty: [['A', 'B'], ['C'], ['D']]

Krok 2: Sprawdzam krawędź C-D (waga: 1)
  ✓ Dodaję do MST (nie tworzy cyklu)
  MST: [('A', 'B', 1), ('C', 'D', 1)]
  Komponenty: [['A', 'B'], ['C', 'D']]

Krok 3: Sprawdzam krawędź B-C (waga: 2)
  ✓ Dodaję do MST (nie tworzy cyklu)
  MST: [('A', 'B', 1), ('C', 'D', 1), ('B', 'C', 2)]
  Komponenty: [['A', 'B', 'C', 'D']]

MST kompletne (3 krawędzi)

Praktyczne zastosowania MST

1. Projektowanie sieci telekomunikacyjnej

Wyjście:

=== Projektowanie sieci telekomunikacyjnej ===

Optymalne połączenia (MST):
  Kraków — Katowice: 80 km
  Wrocław — Poznań: 170 km
  Katowice — Wrocław: 200 km
  Kraków — Wrocław: 270 km
  Warszawa — Kraków: 290 km

Koszt MST: 1010 km kabla
Koszt pełnej sieci: 1670 km kabla
Oszczędności: 660 km (39.5%)

2. Clustering (grupowanie danych)

Wyjście:

=== MST Clustering ===

Przypisanie punktów do 3 klastrów:
  Klaster 0: ['A', 'B', 'C']
  Klaster 1: ['D', 'E', 'F']
  Klaster 2: ['G', 'H']

Porównanie algorytmów Prima i Kruskala

Cecha	Prim	Kruskal
Strategia	Rosnące drzewo	Łączenie lasów
Struktura danych	Kolejka priorytetowa	Union-Find
Złożoność	O(E log V)	O(E log E) = O(E log V)
Sortowanie	❌ Nie	✅ Tak (krawędzie)
Lepszy dla	Grafów gęstych (E ≈ V²)	Grafów rzadkich (E << V²)
Implementacja	Prostsza (bez Union-Find)	Wymaga Union-Find
Równoległość	Trudniejsza	Łatwiejsza (sortowanie + Union-Find)

Praktyczna rada: - Gęsty graf (dużo krawędzi) → Prim - Rzadki graf (mało krawędzi) → Kruskal - W praktyce różnice są małe dla typowych grafów

Dowód poprawności algorytmów

Dlaczego Prim i Kruskal działają?

Oba algorytmy są zachłanne (greedy) i zawsze dają optymalne rozwiązanie. Dlaczego?

Idea dowodu (dla obu): 1. Algorytm zachowuje niezmiennik: W każdym kroku krawędzie w budowanym zbiorze należą do pewnego MST 2. Własność cięcia/cyklu: Wybór najlżejszej krawędzi gwarantuje, że nowa krawędź też należy do MST 3. Na końcu: Mamy drzewo rozpinające (n-1 krawędzi) należące do MST, więc to musi być MST

Dowód przez sprzeczność: Załóżmy, że algorytm zwraca drzewo T, które nie jest MST. Wtedy: - Istnieje MST T* o mniejszej wadze - Ale algorytm zachłanny zawsze wybiera najtańszą opcję (własność cięcia/cyklu) - Sprzeczność! → T musi być MST

Warianty i rozszerzenia MST

1. Maksymalne drzewo rozpinające

Zamiast minimalnego, szukamy maksymalnego drzewa rozpinającego:

2. Drugie najlepsze MST

Znajdź MST o drugiej najmniejszej wadze:

Złożoność i optymalizacje

Złożoność czasowa

Algorytm	Struktura danych	Złożoność
Prim (lista sąsiedztwa)	Bez kolejki	O(V²)
Prim (binary heap)	Binary heap	O(E log V)
Prim (Fibonacci heap)	Fibonacci heap	O(E + V log V)
Kruskal	Union-Find	O(E log E) = O(E log V)

W praktyce: Binary heap wystarczy dla większości zastosowań.

Podsumowanie

Kluczowe cechy MST

Własność	Opis
Definicja	Drzewo rozpinające o minimalnej sumie wag
Liczba krawędzi	n - 1 (gdzie n = liczba wierzchołków)
Niepowtarzalność	MST może nie być unikalne
Algorytmy	Prim (rosnące drzewo), Kruskal (łączenie lasów)
Złożoność	O(E log V) dla obu

Kiedy używać którego algorytmu?

Algorytm Prima: ✅ Grafy gęste (dużo krawędzi) ✅ Reprezentacja: macierz sąsiedztwa ✅ Szukamy MST od konkretnego wierzchołka

Algorytm Kruskala: ✅ Grafy rzadkie (mało krawędzi) ✅ Reprezentacja: lista krawędzi ✅ Proste sortowanie krawędzi ✅ Łatwo równoległe

Co dalej?

Po opanowaniu MST, następne kroki to:

Lekcja 60: Algorytm Bellmana-Forda
Najkrótsza ścieżka z ujemnymi wagami
Wykrywanie cykli ujemnych
Porównanie z Dijkstrą
Algorytm Floyda-Warshalla:
Najkrótsze ścieżki wszystkie pary
Programowanie dynamiczne
Złożoność O(V³)
Przepływy w sieciach:
Algorytm Forda-Fulkersona
Maksymalny przepływ
Minimalne cięcie

Zadania praktyczne

Zadanie 1: Stopień w MST

Udowodnij, że suma stopni wierzchołków w MST wynosi 2(n-1).

Zadanie 2: Liczba MST

Napisz funkcję liczącą wszystkie różne MST w grafie (dla małych grafów).

Zadanie 3: MST z ograniczeniami

Znajdź MST, w którym żaden wierzchołek nie ma stopnia większego niż k.

Zadanie 4: Wizualizacja

Stwórz wizualizację graficzną działania algorytmów Prima i Kruskala krok po kroku.

Zadanie 5: Optymalizacja sieci

Masz sieć miast i możliwe połączenia z kosztami. Znajdź najtańszy sposób połączenia wszystkich miast tak, aby: - Wszystkie miasta były połączone - Każde miasto miało co najmniej 2 połączenia (dla redundancji)

Następna lekcja: Algorytm Bellmana-Forda - najkrótsza ścieżka z ujemnymi wagami