Hallo zusammen,
ich scheitere momentan leider an einer Rekursions-Aufgabe. Es geht darum auszugeben, ob ein Knoten einen anderen "Knoten" über seinen Nachbarn kennt. Sprich ob es einen Weg von Knoten A zu Knoten B gibt. Also eine Art Tiefensuche.
Bsp:
1 2
|/
3-4
Kennt Knoten 4 Knoten 2? ja- über Knoten 3, wobei nur true ausgegeben werden muss. Ein boolean Arraay führt dabei Buch, welcher Knoten schon besucht wurde.
Folgenden Code habe ich bisher, aber es kommt immer ein Stack Overflow und ich weiß nicht genau wo das Problem ist:
ich scheitere momentan leider an einer Rekursions-Aufgabe. Es geht darum auszugeben, ob ein Knoten einen anderen "Knoten" über seinen Nachbarn kennt. Sprich ob es einen Weg von Knoten A zu Knoten B gibt. Also eine Art Tiefensuche.
Bsp:
1 2
|/
3-4
Kennt Knoten 4 Knoten 2? ja- über Knoten 3, wobei nur true ausgegeben werden muss. Ein boolean Arraay führt dabei Buch, welcher Knoten schon besucht wurde.
Folgenden Code habe ich bisher, aber es kommt immer ein Stack Overflow und ich weiß nicht genau wo das Problem ist:
Java:
public boolean sind Verbunden(Knoten k1, Knoten k2) {
boolean verbunden = false;
boolean[] besucht = new boolean[getKnoten().length]; // Anzahl aller Knoten
verbunden = sindVerbunden(k1, k2, besucht);
return verbunden;
}
private boolean sindVerbunden(Knoten von, Knoten zu, boolean[] besucht) {
for (int i = 0; i < getKnoten().length; i++) {
// Hier lege ich den Startknoten fest
if (getKnoten()[i].equals(von)) {
besucht[i] = true;
}
}
// Falls das zutrifft gibt es einen Weg
if (von.equals(zu)) {
return true;
} else {
for (int j = 0; j < getKnoten().length; j++) {
if (!besucht[j] && sindNachbarn(von.getBesitzer(), getKnoten()[j])) { // Sind Nachbarn gibt zurueck ob eine Verbindung besteht
boolean verbunden = sindVerbunden(getProfile(getKnoten()[j]), zu, besucht);
if (verbunden) {
return true;
}
}
}
}
return false;
}