Prim's Algorithm - wo ist der Fehler?

Diskutiere Prim's Algorithm - wo ist der Fehler? im Allgemeine Java-Themen Forum; Hallo zusammen, ich brauche noch ein wenig Java Nachhilfe! Ich will den Prim Algorithmus auf einer Adjazenzliste implementieren, aber irgendwie...

  1. Netty_Zehpunkt
    Netty_Zehpunkt Neues Mitglied
    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 hilft dir dieser Java-Kurs hier weiter --> (hier klicken)
  3. VfL_Freak
    VfL_Freak Bekanntes Mitglied
  4. JCODA
    JCODA Aktives Mitglied
    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.
     
  5. Netty_Zehpunkt
    Netty_Zehpunkt Neues Mitglied
    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:
      3
Die Seite wird geladen...

Prim's Algorithm - wo ist der Fehler? - Ähnliche Themen

Algorithmen - Operation und Eingabegrößen
Algorithmen - Operation und Eingabegrößen im Forum Hausaufgaben
Algorithmus für bessere Kollisionsabfragen
Algorithmus für bessere Kollisionsabfragen im Forum Spiele- und Multimedia-Programmierung
Algorithmus - Strings auf eigene Reihenfolge miteinander vergleichen
Algorithmus - Strings auf eigene Reihenfolge miteinander vergleichen im Forum Java Basics - Anfänger-Themen
Frage Boyer-Moore Algorithmus
Frage Boyer-Moore Algorithmus im Forum Java Basics - Anfänger-Themen
Euklidischer Algorithmus
Euklidischer Algorithmus im Forum Hausaufgaben
Thema: Prim's Algorithm - wo ist der Fehler?