Informatik Algorithmen – Minimaler Spannbaum
Karteikarten zum Thema „Informatik“ · 15 Karten · von atrio. Beispiele: Was ist ein minimaler Spannbaum (MST) eines gewichteten Graphen? · Welche zwei Eigens…
Karten
15 KartenWas ist ein minimaler Spannbaum (MST) eines gewichteten Graphen?
Rückseite
Ein Spannbaum, der alle Knoten verbindet und dessen Summe der Kantengewichte minimal ist unter allen möglichen Spannbäumen.
Welche zwei Eigenschaften kennzeichnen MSTs (Schnitt- und Kreis-Eigenschaft)?
Rückseite
Schnitt-Eigenschaft: Leichteste Kante eines Schnitts gehört zu jedem MST. Kreis-Eigenschaft: Schwerste Kante eines Kreises gehört zu keinem MST.
Wie funktioniert der Algorithmus von Kruskal?
Rückseite
Sortiere alle Kanten aufsteigend nach Gewicht. Füge Kanten hinzu, sofern sie keinen Kreis bilden (Union-Find), bis n-1 Kanten erreicht sind.
Wie funktioniert der Algorithmus von Prim?
Rückseite
Starte mit beliebigem Knoten. Erweitere den Baum iterativ um die leichteste Kante, die einen Baumknoten mit einem Nicht-Baumknoten verbindet (Prioritätswarteschlange).
Was ist der Hauptunterschied zwischen Kruskal und Prim?
Rückseite
Kruskal baut einen Wald zusammenhängender Komponenten (Kanten-sortiert), Prim erweitert einen einzelnen Baum knotenweise (Knoten-fokussiert).
Wie lautet die Laufzeit von Kruskal mit Union-Find und Pfadkompression?
Rückseite
O(|E| log |E|) durch Sortieren der Kanten; Union-Find-Operationen sind nahezu konstant (inverse Ackermann).
Wie lautet die Laufzeit von Prim mit Fibonacci-Heap?
Rückseite
O(|E| + |V| log |V|); mit Binär-Heap O(|E| log |V|).
Wann ist der MST eines Graphen eindeutig?
Rückseite
Genau dann, wenn alle Kantengewichte paarweise verschieden sind (damit entfallen Gleichgewichts-Entscheidungen).
Welche Bedingung muss ein Graph erfüllen, damit ein Spannbaum existiert?
Rückseite
Der Graph muss zusammenhängend sein; andernfalls existiert kein Spannbaum (nur Spannwälder für jede Komponente).
Nenne drei typische Anwendungen minimaler Spannbäume.
Rückseite
Netzwerkdesign (Kabelverlegung), Clustering (Single-Linkage), Approximation für Traveling Salesman Problem (2-Approximation).
Warum eignet sich Kruskal besser für dünne Graphen, Prim für dichte?
Rückseite
Kruskal hängt primär von |E| ab (Sortieren), Prim mit Adjazenzmatrix von |V|²; bei dichten Graphen ist |E| ≈ |V|².
Welche Datenstruktur verhindert Kreise bei Kruskal effizient?
Rückseite
Union-Find (Disjoint Set Union) mit Union by Rank und Pfadkompression für nahezu konstante Amortisationskosten.
Was ist der Algorithmus von Borůvka und wie unterscheidet er sich?
Rückseite
Paralleler Algorithmus: Jede Komponente wählt leichteste ausgehende Kante; läuft in O(|E| log |V|), gut parallelisierbar.
Unterscheidet sich MST vom kürzesten Pfad zwischen zwei Knoten?
Rückseite
Ja: MST minimiert Summe aller Kanten des Baums; kürzester Pfad minimiert Distanz zwischen spezifischem Start und Ziel.
Existiert ein MST-Algorithmus für gerichtete Graphen?
Rückseite
Nicht direkt; für gerichtete Graphen sucht man ein minimales aufspannendes Arboreszenz (Edmonds-Algorithmus/Chu-Liu).