10   Spannbäume

Literatur: Kapitel 24 aus [CLR90].

Inhalt Kantengewichte ·minimale Spannbäume·nimmersatte Strategien (``greedy'') ·Kruskals Algorithmus ·Prims Algorithmus

• Motivation: Verknüpfung¹⁶ einer geg. Anzahl von Knoten mit minimalen Kosten (Verkabelung, Routing, ...)
• Verknüpfung von n Knoten: mit n-1 Kanten
• Kosten: modelliert als "` Kantengewicht"'
• Gegeben:
  • G = (V, E) ungerichtet, zusammenhängend, und mit E Í V × V Menge potentieller Verbindungen
  • Kantengewicht: w: V² ® R.
• Gesucht: TÍ E sodaß
  • azyklisch (Baum)
  • Verbindung aller Knoten (aufspannend, spanning)
  • minimale Kosten

    w(T) =

    å (u,v) Î T

    w(u,v)

    minimal.
• Þ Problem des minimalen Spannbaums
• Beispiel für greedy-Strategie
• Bild

• greedy-Strategie:
  • Heuristik für Optimierungsprobleme
  • falls eine Entscheidung zu treffen ist: entscheide dich für die augenblicklich beste Alternative (ohne auf mögliche Nachfolge-Nachteile zu achten)
• iterativer Aufbau eines minimalen Spannbaumes
• Þ schrittweises Hinzufügen von Kanten.

Generic-MST(G,w) =
  A := 0;
  while A does not form a spanning tree
  do 
    find an edge (u,v) that is safe wrt. A
    A := A $\cup$ {(u,v)}
  done;
  return A

• Problem: wie findet man sichere Kanten?

• während der Algo läuft: A immer azyklisch (Invariante)
• Þ G_A = (V, A) Wald
• zu Beginn: Wald mit |V| (einknotigen) Bäumen
• jede hinzugefügte sichere Kante verknüpft zwei Bäume
• Þ Schleife |V| -1-mal durchlaufen

• G = (V,E) zusammenhängend, ungerichtet, Gewichtungsfunktion W: E ® R.
• A Í E, A Teil eines min. Spannbaumes
• C eine Zusammenhangskomponente (hier Baum) im Wald G_A = (V, A).

• Spezialisierung des generischen Algorithmus'
• greedy-Strategie
• direkt Umsetzung des Korollars 10
• Þ sichere Kante = die mit dem geringsten Gewicht, die zwei Bäume verbindet.
• Þ nimm immer die Kante mit geringstem Gewicht: wenn sie zwei Komponenten verbindet: hinzufügen, wenn nicht, ignorieren
• Hilfsfunktionen + Hilfsdatenstrukturen:
  • Wald = disjunkte Mengen/Partition (von Knoten)
  • find-set: finde Repräsentanten
  • Union: Vereinigung
  • Makeset: ein-elementige Menge

mst-kruskal(G,w) 
  A := 0;                   // A: Kantenmenge
                            // Invariante: A Teil eines min. S-B
  for all $v \in  V[G]$
  do Make-Set(v) done;      // Wald aus lauter Knoten

  sort the edges of $E$ by non-decreasing weight $w$;
 
   for all edges $(u,v) \in E$ (in order)
   do
     if   Find-Set(u) $\not=$ Find-Set(v) // nicht im selben Baum?
     then 
       A := A $\cup$ {(u,v)};// fuege Kante hinzu
       Union(u,v);           // vergroebere Partition
     fi;
   done;
   return A;

• Laufzeit von Kruskal:
• hängt von der Implementierung der Hilfsstukturen ab

  Initialisierung	O(V)
  Sortieren	O(Elog(E))
  innere Schleife	O(E)
  (Datenrepräsentierung	a(E,V)).

• Þ O(Elog(E))¹⁸

• Spezialisierung des generischen Algorithmus'
• A: kein Wald, sondern ein einzelner Baum¹⁹
• Wachsen des Baumes startend von beliebiger Wurzel r
• Baum bestimmt den Schnitt
• Þ Iterationsschitt: füge leichte Kante vom Baum nach außerhalb des Baumes hinzu
• greedy: mit jedem Schritt wird der Baum minimal schwerer
• Datenstruktur
  • Ordnen der Knoten außerhalb des Baumes
  • Þ Priority Queue (z.B. wieder mittels Heap)

mst-prim(G,w,r)            // G = Graph, w = Gewichtung,  r: Wurzel
  Q := V(G);               // priority queue von Knoten
                           // Q : Knoten noch nicht im Baum

  for all $u \in  Q$ do key[u] := $\infty$ done;
  key[r] := 0;                 
  p(r)   := nil;           // r ohne parent
  while  Q $\not= \emptyset$
  do
    u := extract_min(Q);   // u dem Baum hinzugefuegt
    for all $v \in Adj(u)$ // bewerte alle Nachbarn
    do
       if   $v \in$ Q and $w(u,v) < key(v)$
       then p(v)   := u;   // parent
            key(v) := w(u,v)   
       fi
    done
  done