Der Algorithmus von Prim

Einer der einfachsten Algorithmen zur Lösung des Problems minimal aufspannender Bäume ist der Algorithmus von Prim. Benannt wurde dieser Algorithmus nach Robert Prim von den Bell Labs, der ihn 1957 veröffentlichte. Unabhängig von Prim wurde dieser Algorithmus bereits 1930 von Vojtech Jarnik und später 1959 von Edsger Wybe Dijkstra entwickelt.
Die Idee des Algorithmus besteht darin, mit einem beliebigen Knoten anzufangen und davon ausgehend den Baum wachsen zu lassen, indem stets die billigste Kante hinzugefügt wird, die den Baum verlässt. Somit zählt der Algorithmus von Prim zu der Klasse der Greedy-Algorithmen.
Durch diese einfache Struktur des Algorithmus ist er hervorragend geeignet, um ihn mit CindyScript in Visage zu visualisieren. Das folgende Applet zeigt zu jedem konstruierten Graphen das Ergebnis des Algorithmus von Prim an. Versuche es selbst!
 Bitte schalten Sie Java ein, um eine Cinderella-Konstruktion zu sehen. Bitte schalten Sie Java ein, um eine Cinderella-Konstruktion zu sehen.
Das entsprechende Programm sieht in CindySkript überraschend einfach aus:
 
// Algorithmus von Prim
 
//Liste aller Knoten
knoten=allvertices();
 
// Anzahl der Knoten
anz=length(knoten);
 
//Liste aller Kanten
kanten=alledges();
 
// Welche Knoten sind zu Baum verbunden?
// Wähle Startknoten
baumknoten=[knoten_1];
 
//Sortiere Kanten nach Gewicht
kanten=sort(kanten,getweight(#));
 
// Färbe alle Kanten rot
forall(kanten,#.color=[1,0,0]);
 
 
// Wähle n-1 Kanten
forall(1..(anz-1),
 
   // neue Baumkante gefunden?
   neuebaumkante=false;
 
  //suche billigste Kante, die vom Baum wegführt und keinen Kreis schließt 
  forall(kanten,kante,
      // lies die beiden Endknoten der Kante
      vw=incidentvertices(kante);
 
      // welche davon sind schon Baumknoten?
      vwbaum = common(baumknoten,vw);
 
      // Wenn beides Baumknoten ==> Kreis geschlossen, Kante ignorieren!
      // Wenn kein Baumknoten ==> außerhalb vom Baum, Kante ignorieren! 
      // Ansonsten: Baumkante gefunden!
      if(length(vwbaum)==1,
 
           // Wenn noch keine neue Baumkante gefunden wurde in diesem Durchlauf
           if(neuebaumkante==false,
 
              // Baumkante gefunden!
              neuebaumkante = true;
              kante.color=[0,1,0]; // grün!
              // füge den Nicht-Baumknoten zu den Baumknoten
              baumknoten = baumknoten ++ (vw--vwbaum);
          );
     );  
  );
);

< zurück | weiter >