Prim's Algorithm - wo ist der Fehler?

Dieses Thema Prim's Algorithm - wo ist der Fehler? im Forum "Allgemeine Java-Themen" wurde erstellt von Netty_Zehpunkt, 5. Jan. 2017.

Thema: Prim's Algorithm - wo ist der Fehler? Hallo zusammen, ich brauche noch ein wenig Java Nachhilfe! Ich will den Prim Algorithmus auf einer Adjazenzliste...

  1. Hallo zusammen,

    ich brauche noch ein wenig Java Nachhilfe!
    Ich will den Prim Algorithmus auf einer Adjazenzliste implementieren, aber irgendwie klappt das nicht so recht. Er wählt zwar die günstigste Kante aus, aber die ist noch nicht zusammenhängend vom Startpunkt aus.
    Wo liegt da der Fehler? Wie kann man ihn beseitigen?
    Besten Dank im Voraus!
    Code (Java):
    public class Prim {
     
        // Übergabe des Graphen (inkl. Adjazenzmatrix, Eckenanzahl)
        // Array vorgänger um den minimalen Spannbaum zu speichern
        // Array zur Speicherung der Kantengewichte der verbundenen Ecken
        // Array zur Speicherung der Kanten außerhalb des minimalen Spannbaums
        Graph graph;
        int[] vorgaenger;
        int[] keyGewicht;
        boolean[] msbSet;

        // Konstruktor der Primklasse
        public Prim(Graph graph) {
            this.graph = graph;
            this.vorgaenger = new int[graph.getMaxEckenAnzahl()];
            this.keyGewicht = new int[graph.getMaxEckenAnzahl()];
            this.msbSet = new boolean[graph.getMaxEckenAnzahl()];
        }

        // Methode zur Erstellung des minimalen Spannbaums fuer den Graphen
        public void errechneMSBnachPrim() {
         
            // Initialisierung aller Kantengewichte als unendlich
            for (int i = 0; i < graph.getMaxEckenAnzahl(); ++i) {
                this.keyGewicht[i] = Integer.MAX_VALUE;
                this.msbSet[i] = false;
            }
            // Zuweisung des Gewichts fuer Startecke = 0
            // Zuweisung des Vorgaengers fuer Startecke = -1 (Wurzel)
            this.keyGewicht[0] = 0;
            this.vorgaenger[0] = -1;
         
            // Für jede Ecke des minimalen Spannbaums
            for (int i = 0; i < graph.getMaxEckenAnzahl() - 1; i++) {
             
             
                // Nehme die Kante mit dem kleinsten Gewicht
                // Setze die Kante auf besucht
                int u = MinGewicht(this.keyGewicht, this.msbSet);
                this.msbSet[u] = true;
             
                // Aktualisiere das Gewicht und den Vorgaenger der
                // gewaehlten Kante
                for (int v = 0; v < graph.getMaxEckenAnzahl(); ++v) {
                 
                    // Nur Aktualisieren, wenn Kante verbunden (Matrix != 0)
                    // Ecke noch nicht als besucht markiert (msbSet == false)
                    // und das reale Kantengewicht kleiner ist als das zugewiesene
                    if (graph.getGewAdjazenzmatrix()[u][v] != 0 && this.msbSet[v] == false
                            && graph.getGewAdjazenzmatrix()[u][v] < this.keyGewicht[v]) {
                        this.vorgaenger[v] = u;
                        this.keyGewicht[v] = graph.getGewAdjazenzmatrix()[u][v];
                    }
                }
            }

             Print();
        }

        // Eine Hilfsfunktion um die Kante des kleinsten Wertes
        // zu finden aus dem Kantenarray, dass noch nicht
        // im minimalen Spannbaum zu finden ist.
        private int MinGewicht(int[] key, boolean[] msbSet) {

            // Initialisierung des kleinsten Wertes
            int min = Integer.MAX_VALUE, minIndex = -1;

            for (int v = 0; v < graph.getMaxEckenAnzahl(); v++) {
                if (msbSet[v] == false && key[v] < min) {
                    min = key[v];
                    minIndex = v;
                }
            }

            return minIndex;
        }

        // Eine Hilfsfunktion, um den minimalen Spannbaum auszugeben
        // der im Array vorgaenger gespeichert wurde
        private void Print() {
            System.out.println("Ecke     Gewicht");
            for (int i = 1; i < graph.getMaxEckenAnzahl(); ++i)
                System.out
                        .println(this.vorgaenger[i] + " - " + i + "    " + graph.getGewAdjazenzmatrix()[i][vorgaenger[i]]);
        }

    }
     
    Zuletzt von einem Moderator bearbeitet: 6. Jan. 2017
  2. Vielleicht helfen dir diese Java-Grundlagen weiter --> *Klick*
  3. Ich wäre wesentlich motivierter mich damit zu beschäftigen, wenn ich den Code ausführen kann, d.h. die Graph-Klasse und alles weitere zur Verfügung gestellt wird.
     
  4. Oha, auch wenn ich jetzt ärger kriege (da man ja keine kompletten Projekte zur Verfügung stellen soll),
    hier ist mein "Projekt" inkl meine Graphenklasse und der Primklasse.

    Er funktioniert zwar (findet den minimalen Spannbaum), aber mit dem beispielhaften Testgraphen läuft er nicht ganz richtig.
     

    Anhänge:

    • algo.zip
      Dateigröße:
      3,9 KB
      Aufrufe:
      2
  5. KOSTENLOSES Java-Grundlagen Training im Wert von 39 € Sichere dir hier den kostenlosen Zugriff auf umfangreiches Java-Know How und starte richtig durch!