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:
Setze farbnummer auf 1
Hole eine Liste aller Kanten und sortiere sie aufsteigend
Wiederhole für jede Kante
  k1 = Startknoten, k2 = Zielknoten der Kante
  Falls Farbe von k1==0 und Farbe von k2==0 
    Setze Farbe beider Knoten auf farbnummer
    Markiere die Kante
    Erhöhe die Farbnummer um 1
  Sonst
    Falls Farbe eines Knotens==0
      Setze Farbe dieses Knotens auf die des anderen
      Markiere die Kante
    Sonst
      Falls beide Knoten unterschiedliche Farben haben
        Wiederhole für jeden Knoten k im Graph
          Falls Farbe von k die Farbe von k2 hat
            Setze Farbe von k auf die Farbe von k1
          Ende-Falls
        Ende-Wiederhole
        Markiere die Kante
      Sonst
        Lösche Kante
      Ende-Falls
    Ende-Falls

int farbe = 1;
List<Kante> kanten = g.getAlleKanten();
List<Knoten> knoten = g.getAlleKnoten();
Collections.sort(kanten);
 
for (Kante k: kanten) {
  int f1 = k.getStart().getFarbe();
  int f2 = k.getZiel().getFarbe();
  if(f1 == 0 && f2 == 0) {
    k.getStart().setFarbe(farbe);
    k.getZiel().setFarbe(farbe);
    k.setMarkiert(true);
    farbe++;
  } else
  if(f1 == 0) {
    k.getStart().setFarbe(f2);
    k.setMarkiert(true);
  } else
  if(f2 == 0) {
    k.getZiel().setFarbe(f1);
    k.setMarkiert(true);
  } else
  if(f1 == f2) {
    k.setGeloescht(true);
  } else 
  {
    for(Knoten k1 : knoten) {
      if(k1.getFarbe() == f2) k1.setFarbe(f1);
    }
    k.setMarkiert(true);
  }
}