Minimaler Spannbaum

Original-Landkarte

Minimaler Spannbaum

Definition

Ein Minimaler Spannbaum besteht aus einer Liste von Kanten des Graphen, die folgenden Bedingungen genügen muss:

1. die Kanten der Liste müssen alle Knoten des Graphen miteinander verbinden.
2. die Gesamtlänge der Kanten in der Liste muss (im Hinblick auf die Erfüllung der 1. Bedingung) minimal sein.

Beispiel aus der Praxis

Eine Stromfirma will ein Leitungsnetz aufbauen, das alle Städte verbindet. Keine Stadt darf ausgelassen werden. Das Stromnetz soll aber möglichst kurz sein.

Implementierung

1. Zu Anfang erzeugt man einen ergebnisgraph, der nur die Knoten des ursprünglichen Graphen enthält, aber nicht die Kanten.
2. Alle Kanten des gesamten ursprünglichen Graphen werden ausgelesen werden ihrem Gewicht nach durchgegangen, wobei man beim kleinsten Gewicht anfängt.
   1. Kann die momentan betrachtete Kante in den ergebnisgraph eingefuegt werden, ohne dass ein Kreis entsteht, wird sie eingefügt.

Hauptmethode

 public Graph minimalerSpannbaum(Graph pGraph){
    //es wird ein neuer Graph erstellt, der das Ergebnis hinterher anzeigt
    Graph ergebnisGraph = new Graph();
    //alle Knoten des uebergebenen Graphen werden
    //in den spaeteren Ergebnisgraphen eingetragen
    List nodes = pGraph.getNodes();
    nodes.toFirst();
    while(nodes.hasAccess()){
       GraphNode akt = (GraphNode)nodes.getObject();
       ergebnis.addNode(akt);
       nodes.next();
    }
    List edges = alleEdgesSortiert(pGraph);
    //diese Liste wird duchgegangen
    for(edges.toFirst(); edges.hasAccess(); edges.next()){
    //kann die aktuell in der Liste betrachtete Kante eingefuegt werden,
    //ohne dass ein Kreis entsteht, wird sie eingefuegt    
    Edge akt = (Edge)edges.getObject();
       if(!erzeugtKreis(ergebnisGraph, edges.elementAt(i))){
          ergebnisGraph.addEdge(akt.getNodeA(), akt.getNodeB(), akt.getWeight());
          System.out.println("addEdge: "+akt);
       }
    }
    return ergebnisGraph;
 }

Hilfsmethoden

Für die Überpruefung ob ein Kreis erzeugt wird ist eine eigene Methode hilfreich. Hier wird von einem Knoten der einzufuegenden Kantre ausgehend ueberprueft, ob der andere Knoten erreichbar ist. Wenn ja, dann würde durch Einfügen ein Kreis erzeugt, wenn nein nicht.

 private boolean erzeugtKreis(Graph pGraph, Edge pEdge) {
    //von dem einen Knoten aus erreichbare Nodes
    //werden ausgelesen un in einer Liste gespeichert...
    List erreichbare = erreichbareNodes(pGraph, pEdge.getNodeA());
    //...und werden durchlaufen
    erreichbare.toFirst();
    while(erreichbare.hasAccess()){
       //wird der Knoten, von dem ausgegangen wurde, gefunden,
       //wurde ein Kreis erzeugt und true ausgegeben
       if(pEdge.getNodeB() == (GraphNode)erreichbare.getObject()){
          return true;
       }
       erreichbare.next();
    }
    //wird der Knoten nicht gefunden, wird false zurueckgegeben,
    //da kein Kreis erzeugt wuerde
    return false;
 }