Prim-Algorithmus: Unterschied zwischen den Versionen

Aus KGS-Wiki
K (Graph-Layout)
 
(2 dazwischenliegende Versionen desselben Benutzers werden nicht angezeigt)
Zeile 1: Zeile 1:
{{Thumbnailbox|
{{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}}
|CAPTION=Ein Beispielgraph}}


Zeile 35: Zeile 22:
|INHALT=
|INHALT=
{{Thumbnailbox|
{{Thumbnailbox|
INHALT={{#mermaid:graph LR
INHALT={{Beispielgraph|link=lightgray}}
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
linkStyle default stroke:lightgray, fill:none;
}}
|CAPTION=Vorbereitung: <math>T</math> ist noch leer.
|CAPTION=Vorbereitung: <math>T</math> ist noch leer.
|ALIGN=left
|ALIGN=left
Zeile 55: Zeile 28:


{{Thumbnailbox|
{{Thumbnailbox|
INHALT={{#mermaid:graph LR
INHALT={{Beispielgraph|link=lightgray|C=#00B169}}
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
style c fill:#00B169;
linkStyle default stroke:lightgray, fill:none;
}}
|CAPTION=Schritt 1: wähle zufälligen Knoten und füge ihn zu <math>T</math> hinzu.
|CAPTION=Schritt 1: wähle zufälligen Knoten und füge ihn zu <math>T</math> hinzu.
|ALIGN=left
|ALIGN=left
Zeile 76: Zeile 34:


{{Thumbnailbox|
{{Thumbnailbox|
INHALT={{#mermaid:graph LR
INHALT={{Beispielgraph|link=lightgray|C=#00B169|AC=#00B169|A=#00B169}}
a((A))
|CAPTION=Schritt 2: von allen Kanten, die einen Knoten in <math>T = \left\lbrace C\right\rbrace</math> mit einem anderen<br>Knoten verbinden, hat <math>\overline{AC}</math> das kleinste Gewicht. Füge <math>A</math> und <math>\overline{AC}</math> zu <math>T</math> hinzu.
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
style c fill:#00B169;
style a fill:#00B169;
linkStyle default stroke:lightgray, fill:none;
linkStyle 2 stroke:#00B169, fill:none;
}}
|CAPTION=Schritt 2: füge <math>A</math> und <math>\overline{AC}</math> zu <math>T</math> hinzu.
|ALIGN=left
|ALIGN=left
|CLASS=noclear}}
|CLASS=noclear}}


{{Thumbnailbox|
{{Thumbnailbox|
INHALT={{#mermaid:graph LR
INHALT={{Beispielgraph|link=lightgray|C=#00B169|AC=#00B169|A=#00B169|CD=#00B169|D=#00B169}}
a((A))
|CAPTION=Schritt 3: von allen Kanten, die einen Knoten in <math>T = \left\lbrace A, C\right\rbrace</math> mit einem anderen<br>Knoten verbinden, hat <math>\overline{CD}</math> das kleinste Gewicht. Füge <math>D</math> und <math>\overline{CD}</math> zu <math>T</math> hinzu.
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
style c fill:#00B169;
style a fill:#00B169;
style d fill:#00B169;
linkStyle default stroke:lightgray, fill:none;
linkStyle 2 stroke:#00B169, fill:none;
linkStyle 5 stroke:#00B169, fill:none;
}}
|CAPTION=Schritt 3: füge <math>D</math> und <math>\overline{CD}</math> zu <math>T</math> hinzu.
|ALIGN=left
|ALIGN=left
|CLASS=noclear}}
|CLASS=noclear}}


{{Thumbnailbox|
{{Thumbnailbox|
INHALT={{#mermaid:graph LR
INHALT={{Beispielgraph|link=lightgray|C=#00B169|AC=#00B169|A=#00B169|CD=#00B169|D=#00B169|AB=#00B169|B=#00B169}}
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
style c fill:#00B169;
style a fill:#00B169;
style d fill:#00B169;
style b fill:#00B169;
linkStyle default stroke:lightgray, fill:none;
linkStyle 2 stroke:#00B169, fill:none;
linkStyle 5 stroke:#00B169, fill:none;
linkStyle 0 stroke:#00B169, fill:none;
}}
|CAPTION=Schritt 4: füge <math>B</math> und <math>\overline{AB}</math> zu <math>T</math> hinzu.
|CAPTION=Schritt 4: füge <math>B</math> und <math>\overline{AB}</math> zu <math>T</math> hinzu.
|ALIGN=left
|ALIGN=left
Zeile 151: Zeile 52:


{{Thumbnailbox|
{{Thumbnailbox|
INHALT={{#mermaid:graph LR
INHALT={{Beispielgraph|link=lightgray|C=#00B169|AC=#00B169|A=#00B169|CD=#00B169|D=#00B169|AB=#00B169|B=#00B169|BE=#00B169|E=#00B169}}
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
style c fill:#00B169;
style a fill:#00B169;
style d fill:#00B169;
style b fill:#00B169;
style e fill:#00B169;
linkStyle default stroke:lightgray, fill:none;
linkStyle 2 stroke:#00B169, fill:none;
linkStyle 5 stroke:#00B169, fill:none;
linkStyle 0 stroke:#00B169, fill:none;
linkStyle 4 stroke:#00B169, fill:none;
}}
|CAPTION=Schritt 5: füge <math>E</math> und <math>\overline{BE}</math> zu <math>T</math> hinzu.
|CAPTION=Schritt 5: füge <math>E</math> und <math>\overline{BE}</math> zu <math>T</math> hinzu.
|ALIGN=left
|ALIGN=left
Zeile 184: Zeile 62:
== Weblinks ==
== Weblinks ==


* [https://visualgo.net/en/mst Visuelle Darstellung des Prim-Algorithmus auf VisuAlgo.net 🇬🇧]
* {{VisuAlgo|en/mst|Der Prim-Algorithmus visualisiert}}
{{Navigationsleiste Graphalgorithmen}}
{{Navigationsleiste Graphalgorithmen}}
[[Kategorie:Graphen]]
[[Kategorie:Graphen]]
[[Kategorie:Algorithmen]]
[[Kategorie:Algorithmen]]

Aktuelle Version vom 1. April 2024, 01:41 Uhr

Ein Beispielgraph

Der Prim-Algorithmus ist ein Algorithmus, der zu einem gegebenen gewichteten Graphen einen minimalen Spannbaum berechnet.

Der Algorithmus wurde 1930 von Vojtěch Jarník entwickelt, 1957 vom namensgebenden Robert Prim und 1959 noch einmal von Edsger Dijkstra wiederentdeckt und funktioniert folgendermaßen:

  1. Wir beginnen mit einem leeren Spannbaum , den wir uns im Folgenden zusammenbasteln.
  2. Wähle zufällig einen Knoten aus dem Graphen und füge ihn zu hinzu.
  3. Solange noch nicht alle Knoten enthält, wiederhole folgende Schritte:
    1. Betrachte alle Kanten, die einen Knoten in mit einem Knoten, der nicht in ist, verbinden.
    2. Wähle von diesen Kanten eine mit dem kleinsten Gewicht
    3. Füge diese Kante und den daran hängenden Knoten, der noch nicht in ist, zu hinzu.

ist dann ein minimaler Spannbaum.

Beispiel

So erzeugt der Prim-Algorithmus aus dem Beispielgraphen einen MST:

Vorbereitung: ist noch leer.
Schritt 1: wähle zufälligen Knoten und füge ihn zu hinzu.
Schritt 2: von allen Kanten, die einen Knoten in mit einem anderen
Knoten verbinden, hat das kleinste Gewicht. Füge und zu hinzu.
Schritt 3: von allen Kanten, die einen Knoten in mit einem anderen
Knoten verbinden, hat das kleinste Gewicht. Füge und zu hinzu.
Schritt 4: füge und zu hinzu.
Schritt 5: füge und zu hinzu.

Nach Schritt 5 enthält der Baum alle Knoten und erfüllt damit die Kriterien für einen Spannbaum.

Weblinks

Abgerufen von „https://wiki.kah.gs/index.php?title=Prim-Algorithmus&oldid=4117“