Algorithmus von Kruskal zur Bestimmung eines MST

Beschreibung des Algorithmus (Kruskal)

Der Algorithmus verfolgt die Idee, immer die kürzeste Kante des Graphen dem Baum hinzuzufügen, wenn dadurch nicht ein Zyklus entsteht und die Kante damit überflüssig ist. Es entstehen dabei zunächst viele einzelne Bäume (ein Wald), die sukzessive zu einem einzigen Baum zusammengeführt werden. Um die Zyklen leicht erkennen zu können, werden die Knoten jedes einzelnen Baums in einer eigenen Farbe eingefärbt. Zunächst werden die Kanten also nach ihrem Gewicht sortiert und dann für jede Kante folgende Regeln beachtet:

• haben beide Knoten noch keine Farbe (Farbe 0), dann gehören sie bisher zu keinem Baum und werden beide in einer noch nicht benutzen Farbe gefärbt.
• hat ein Knoten eine Farbe und der andere noch nicht, wird der Baum des farbigen Knotens erweitert. Die Farbe wird für den noch nicht gefärbten Knoten übernommen.
• haben beide Knoten eine unterschiedliche Farbe, dann werden zwei Bäume zu einem vereinigt. Alle Knoten des zweiten Baums werden mit der Farbe des ersten eingefärbt.
• haben beide Knoten die gleiche Farbe, gehören sie zum gleichen Baum. Die Kante darf nicht eingefügt werden, da ein Zyklus entstehen würde.

Außer in Fall 4 wird außerdem die Kante markiert, da sie zum minimalen Spannbaum gehört.

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);
  }
}