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!
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!
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 bearbeitet von einem Moderator:
