Rekursion Tiefensuch-Problem - Stack Overflow

[Fero]

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:

	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;
	}

 

[Dekker]

öhm. Wie speicherst du die Knoten genau? Im Grunde genommen speichert man Graphen entweder als Adjazentmatrix oder Adjazenzliste. Ich muss ehrlich sein,ich verstehe garnicht was du da überprüfst und machst, weil ich den ganzen Restlichen Code nicht kenne.

Dein Problem ist das du viele rekursive Aufrufe hast (immerhin hast du jedesmal eine Schleife die alle Knoten durchprobiert) und übergibst immer ein ganzes Array. Was beim rekursiven Aufruf passiert ist das dein Array jedesmal auf dem Stack gespeichert werden muss, damit er beim zurückkehren auf die jeweils vorherige Aufrufebene wieder den Aktuellen Array kennt. Das Kostet natürlich viel Platz. Eine Möglichkeit dagegen wäre nicht den Array zu übergeben sondern den Array als globale Variable zu setzen.

 

[Fero]

Hallo,

danke schon einmal für deine Antwort. Die Knoten sind alle in einem Array gespeichert. Es werden nun zwei beliebige Knoten übergeben und nun soll ermittelt werden, ob diese Knoten über andere Knoten erreichbar sind und sich so "kennen".



Gehen wir mal von dem erweiterten Beispiel aus:

1-2

|

3-4-5

Nun soll ermittelt werden, ob der Knoten 1, Knoten 4 kennt. Ich habe mir das nun so überlegt:

- Knoten 1 ist der Anfangsknoten

- Nun wird der 2. Knoten überprüft ob er Verbunden mit Knoten 1 ist -> Das ist er in diesem Fall, also wird das im Boolean-Array vermerkt

- Nun wird von dem 2. Knoten nach weiteren Nachbarn geschaut, gibt es nicht, also soll nun wieder der Rücksprung auf Knoten 1 erfolgen.

- Da Knoten 1 nun schon Knoten 2 besucht hat und das mit einem wahr im Boolean-Array vermerkt wurde, springt man nun zu Knoten 3, da hier ebenfalls eine Verbindung besteht, was ebenfalls vermerkt wurde

- usw.

Das mit den zu vielen Aufrufen habe ich mir schon gedacht, ich denke der Rücksprung klappt einfach nicht, ich weiß nur nicht wieso ...

-

 

[Firephoenix]

Poste mal bitte deine Datenstruktur Knoten und den Rest der Klasse (zumindest die nötigen methoden und Datenfelder für die Aufgabe), dann kann man leicher einschätzen an welcher Stelle man mit dem rekursiven Aufruf ansetzen kann.

Wichtig im Algorythmus ist auch, ob ihr Zyklen zwischen den Knoten haben könnt oder nicht - falls nicht brauchst du eigentlich keine besuchten Knoten zu verwalten was wieder Platz spart.

An sich würde ich so eine Struktur versuchen (Pseudocode und ohne Zyklen)

public boolean sindVerbunden(Knoten k1, Knoten k2) {
        für(alle Nachbarknoten kN von k1){
            if(kN = k2)
                return true;
            else{
                return sindVerbunden(kN , k2);
            }
        }
        return false;
    }

Gruß

 

[Fero]

Die Klasse ist zu umfangreich, deshalb macht es eher keinen Sinn, sie komplett zu posten. Im Grunde ist wie schon gesagt folgendes vorhanden:


Array mit Knoten - Beinhaltet alle Knoten
getKnoten - Zugriff auf die Knoten (Array)

Array mit allen Nachbarn eines Knoten
getNachbar - Zugriff auf alle Nachbarn (Array)



Methode sindVerbunden(k1, k2) - gibt aus ob die beiden Knoten direkt verbunden sind.


Zyklen können entstehen, wäre aber erst einmal egal, denn selbst mit deinem Vorschlag bekomme ich einen Stack Overflow. Folgendermaßen habe ich deinen Vorschlag umgesetzt:

private boolean sindVerbunden(Knoten von, Knoten zu) {

		for (int i = 0; i < von.getNachbar().length; i++) {
			if (von.getNachbar()[i].equals(zu)) {
				return true;
			} else {
				return sindVerbunden(von.getNachbar()[i], zu);
			}
		}
		return false;

	}

Habe zum Testen extra keine Zyklen eingebaut, dennoch kommt wieder ein Stack overflow ...

 

[Firephoenix]

Da musst du aufpassen wenn du ungerichtete Kanten hast, diese ergeben auch Zyklen -> taucht k1 wieder als Nachbar von kN auf musst du in dem Fall den Schleifendurchlauf überspringen oder du drehst dich zwischen den 2 Knoten so lange im Kreis bis der Stack voll ist.
Gruß

 

[Fero]

Ja sind ungerichtete Kanten, könnte mir gut vorstellen das es daran liegt. Aber irgendwie stehe ich gerade auf dem Schlauch, wie ich das Abfange. Kannst du mir das sagen, wie und wo ich das in der sindVerbunden()-Methode prüfen kann?

 

[Firephoenix]

Da wirst du mit den 2 Parametern nicht mehr hinkommen sondern am besten auf der Version mit dem besucht-Array erweitern (alternativ wäre eine List wohl besser als Datenstruktur).
Dann fügst du direkt beim Aufruf deinen Startknoten zu der besucht-Liste hinzu und bei der Schleife prüfst du ob kN in der besucht-List enthalten ist, falls ja überspringst du diesen Knoten (z.B. per continue)

 

[Fero]

Naja, so war es in meiner ersten Version ja auch ursprünglich geplant 😉 Den Vorschlag mit der Liste muss ich leider ablehnen, da mir die Methoden-Signatur so vorgegeben wurde.


Ich werde mir das noch einmal anschauen und nochmal umändern, hoffentlich passt es dann.


Danke auf jeden Fall schon einmal für deine Hilfe!

 

[Fero]

So ich wollt mich noch einmal zurückmelden, ich habe es nun doch tatsächlich geschafft :applaus:

Habs nun genauso umgesetzt wie Firephoenix es vorgeschlagen hat und nach dem ich auch noch ein paar Stolpersteine aus den Weg räume konnte, funktioniert es nun auch endlich sogar ohne Stack overflow :toll:


Besten Dank noch mal an dich Firephoenix, warst echt eine Bombenhilfe!