Borůvka-Algorithmus: Unterschied zwischen den Versionen

Version vom 4. Dezember 2023, 01:17 Uhr

Ein Beispielgraph

Der Borůvka-Algorithmus ist ein Algorithmus, der zu einem gegebenen gewichteten Graphen einen minimalen Spannbaum erzeugt.

Der Algorithmus wurde 1926 von Otakar Borůvka entworfen und arbeitet wie folgt:

Gegeben sei ein Graph G.
Erzeuge einen neuen Graphen T, der später der gesuchte Spannbaum wird.
Füge alle Knoten, aber keine Kanten des Graphen G zu T hinzu.
Wiederhole die folgenden Schritte, bis T zusammenhängend ist:
1. Füge zu jeder Zusammenhangskomponente von T deren kleinste ausgehende Kante in G hinzu.

So erzeugt der Borůvka-Algorithmus aus dem Beispielgraphen einen MST:

Da $T$ nun zusammenhängend ist, terminiert der Algorithmus.

@@ Zeile 1: / Zeile 1: @@
 {{Thumbnailbox|
-INHALT={{#mermaid:graph LR
+INHALT={{Beispielgraph}}
-a((A))
-b((B))
-c((C))
-d((D))
-e((E))
-a -- 3 --- b
-b -- 7 --- c
-a -- 1 --- c
-b -- 5 --- d
-b -- 1 --- e
-c -- 2 --- d
-d -- 7 --- e
-}}
 |CAPTION=Ein Beispielgraph}}