Algorithmus von Prim

Beschreibung des Algorithmus (Prim)

Dieser Algorithmus startet mit einem beliebigen Knoten. Dieser wird markiert. Sukzessive werden an diesen Knoten weitere Knoten angebunden und so allmählich ein immer größerer Baum aufgebaut. Dabei wird derjenige Knoten dem Baum hinzugefügt, zu dem die kürzeste Kante vom bisherigen Baum führt. Diese Kante wird markiert.

Auch hier startet man damit, die Kanten nach ihrem Gewicht zu sortieren. Nun sucht man in dieser Liste nach einer Kante, bei der ein Knoten markiert ist und der andere nicht. Dabei kann man alle Kanten, bei denen beide Knoten markiert sind, streichen, da sie nie mehr gebraucht werden.

Hat man eine derartige Kante gefunden, wird sie markiert und aus der Liste entfernt. Der neu angebundene Knoten wird ebenfalls markiert. Diese Schritte wiederholt man, bis alle Knoten angebunden sind, also n-1 mal bei n Knoten.

Minimal spanning tree:
Hole eine Liste aller Kanten und sortiere sie aufsteigend
Setze einen beliebigen Knoten auf markiert
Wiederhole n-1 mal * Versuche herauszufinden, wie der Algorithmus funktioniert, indem du ihn Schritt für Schritt ausführst.
  * Welche Situation muss vermieden werden? Fällt dir dafür eine einfache Lösung ein.
  * Beschreibe deinen so gefundenen Algorithmus in einem kurzen Text.
  * Vergleiche deine Beschreibung mit den Musterlösung (unten) und bewerte, ob du das Vorgehen richtig nachvollzogen hast.
  Wiederhole für jede Kante ka der Liste
    Falls Markierung des Startknotens != Markierung des Zielknotens
      naechsteKante = ka
      brich Schleife ab
    Ende-Falls
  Ende-Wiederhole
  Markiere naechsteKante und lösche sie aus der Liste
  Markiere Start- und Zielknoten
Ende Wiederhole

List<Knoten> knoten = g.getAlleKnoten();
List<Kante> kanten = g.getAlleKanten();
Collections.sort(kanten);
knoten.get(0).setMarkiert(true);
 
for(int i = 1; i<knoten.size(); i++) {
  Kante ka=null;
  for(Kante ka2 : kanten) {
    if(ka2.getStart().isMarkiert() != ka2.getZiel().isMarkiert()) {
      ka = ka2;
      break;
    }
  }
 
  ka.setMarkiert(true);
  kanten.remove(ka);
  ka.getStart().setMarkiert(true);
  ka.getZiel().setMarkiert(true);
}