Prim-Algorithmus: Unterschied zwischen den Versionen

Aus KGS-Wiki
K (Kategorien)
(Beispiel begonnnen)
Zeile 20: Zeile 20:
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:
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:


#Wir beginnen mit einem leeren Spannbaum <code>T</code>, den wir uns im Folgenden zusammenbasteln.
#Wir beginnen mit einem leeren Spannbaum <math>T</math>, den wir uns im Folgenden zusammenbasteln.
#Wähle zufällig einen Knoten aus dem Graphen und füge ihn zu <code>T</code> hinzu.
#Wähle zufällig einen Knoten aus dem Graphen und füge ihn zu <math>T</math> hinzu.
#Solange <code>T</code> noch nicht alle Knoten enthält, wiederhole folgende Schritte:
#Solange <math>T</math> noch nicht alle Knoten enthält, wiederhole folgende Schritte:
##Betrachte alle Kanten, die einen Knoten in <code>T</code> mit einem Knoten, der nicht in <code>T</code> ist, verbinden.
##Betrachte alle Kanten, die einen Knoten in <math>T</math> mit einem Knoten, der nicht in <math>T</math> ist, verbinden.
##Wähle von diesen Kanten eine mit dem kleinsten Gewicht
##Wähle von diesen Kanten eine mit dem kleinsten Gewicht
##Füge diese Kante und den daran hängenden Knoten, der noch nicht in <code>T</code> ist, zu <code>T</code> hinzu.
##Füge diese Kante und den daran hängenden Knoten, der noch nicht in <math>T</math> ist, zu <math>T</math> hinzu.
<code>T</code> ist dann ein minimaler Spannbaum.
<math>T</math> ist dann ein minimaler Spannbaum.
 
== Beispiel ==
 
So erzeugt der Prim-Algorithmus aus dem Beispielgraphen einen MST
 
{{Hinweisbaustein|style=border: none; padding: none
|INHALT=
{{Thumbnailbox|
INHALT={{#mermaid:graph LR
a((A))
b((B))
c((C))
d((D))
e((E))
a -- 3 --- b
a -- 1 --- c
b -- 7 --- c
b -- 5 --- d
b -- 1 --- e
c -- 2 --- d
d -- 7 --- e
linkStyle default stroke:lightgray, fill:none;
}}
|CAPTION=Schritt 1: <math>T</math> ist noch leer.}}
}}
 
{{Lückenhaft}}


== Weblinks ==
== Weblinks ==

Version vom 30. März 2023, 15:34 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

Schritt 1: ist noch leer.
🕳
Lückenhaft

In diesem Artikel oder Abschnitt fehlen noch wichtige Informationen.

Hilf dem KGS-Wiki, indem du sie recherchierst und einfügst.

Weblinks

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