Borůvka-Algorithmus: Unterschied zwischen den Versionen

Version vom 31. März 2023, 08:48 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 89: / Zeile 89: @@
 {{Thumbnailbox|
 INHALT={{#mermaid:graph LR
+subgraph acd["{A, C, D}"]
 a((A))
-b((B))
 c((C))
 d((D))
+end
+subgraph be["{B, E}"]
+b((B))
 e((E))
+end
 a -- 3 --- b
 a -- 1 --- c
@@ Zeile 107: / Zeile 111: @@
 style d stroke:red;
 style e stroke:green;
+style acd stroke:red, stroke-width: 3px;
+style be stroke:green, stroke-width: 3px;
 linkStyle default stroke:lightgray, fill:none;
 linkStyle 1 stroke:red, stroke-width: 3px;
@@ Zeile 118: / Zeile 124: @@
 {{Thumbnailbox|
 INHALT={{#mermaid:graph LR
+subgraph acd["{A, C, D}"]
 a((A))
-b((B))
 c((C))
 d((D))
+end
+subgraph be["{B, E}"]
+b((B))
 e((E))
+end
 a -- 3 --- b
 a -- 1 --- c
@@ Zeile 136: / Zeile 146: @@
 style d stroke:red;
 style e stroke:green;
+style acd stroke:red, stroke-width: 3px;
+style be stroke:green, stroke-width: 3px;
 linkStyle default stroke:lightgray, fill:none;
 linkStyle 1 stroke:red, stroke-width: 3px;
@@ Zeile 148: / Zeile 160: @@
 {{Thumbnailbox|
 INHALT={{#mermaid:graph LR
+subgraph abcde["{A, B, C, D, E}"]
 a((A))
 b((B))
@@ Zeile 160: / Zeile 173: @@
 c -- 2 --- d
 d -- 7 --- e
+end
 classDef default stroke:red, stroke-width: 3px;linkStyle default stroke:lightgray, fill:none;
+style abcde stroke:red, stroke-width: 3px;
 linkStyle 1 stroke:red, stroke-width: 3px;
 linkStyle 4 stroke:red, stroke-width: 3px;