Frage zu Graph Tiefensuche

[Luk10]

Grüße,

Ich habe einen Graphen mit, wie üblich, einer Knotenliste als

Knoten[]

.
Nun habe ich folgende Aufgabe / Problem:

Ich soll eine

ArrayList<Knoten>

ausgeben, welche die Knoten eines möglichen Weges (Also nicht der kürzeste) von

start_index

bis

ziel_index

in richtiger Reihenfolge enthält.

Ich würde dazu gerne die Tiefensuche verwenden, da ich die verstanden habe und auch umsetzten kann. Nur wie mache ich das am besten mit den Knoten speichern, die ich durchlaufen habe?

Wie kann ich die Knoten speichern, wenn die Methode rekursiv aufgerufen wird? Mit einer Instanzvariablen? Das finde ich aber nicht besonders "schön" da ich ja eigentlich nur per Methode die Liste zurückgeben will.

Kann mir jemand einen Denkanstoß / Tipps geben wie ich sowas lösen kann?

Hier meine Tiefensuche:

public void depthFirstSearch(int start_index, int end_index) {
		
		if (start_index != end_index) {
			
			for(int i = 0; i < nodelist.length; i++) {
				if (adjacencyMatrix[start_index][i] != null && !nodelist[i].isVisited()) {
					//Do something
					depthFirstSearch(i, end_index);
				}
			}
		}
	}

P.S. Falls jemand "unschöne" englische Bezeichnungen auffallen, bitte bescheid geben 😳

Danke,
-Luk-

 

[SlaterB]

die einzigen beiden Alternativen zu einem Instanzattribut sind offensichtlich ein statisches Attribut oder ein Methodenparameter, der rekursiv übergeben wird,

Instanzattribut ist übrigens gar nicht so schlimm, bei einer derart komplizierten Aufgabe mit vielleicht hunderten bis tausenden Aufrufen darf gerne das ganze Objekt nur dem einzigen Zweck einer einzelnen Suche dienen,

da ist z.B. die Objekterzeugung überhaupt kein nennenswerter Aufwand,
vielleicht die Übertragung/ doppelte Datenhaltung der adjacencyMatrix/ nodelist usw. ein Hinderungsgrund

bedenke auch immer dass du mehrere Methoden nutzen kannst:

public Result search() {
   init parameter
   searchIntern(parameter);
   return result
}

private void searchIntern(parameter) {
  ..
}

 

[Luk10]

Okay, danke schonmal!

Was meinst du mit

vielleicht die Übertragung/ doppelte Datenhaltung der adjacencyMatrix/ nodelist usw. ein Hinderungsgrund

?

Ich denke ich werde dann doch die meiner Meinung nach einfachsten weg über eine Instanzvariable nehmen ... wenn das also doch in Ordnung ist 😉

-Luk10-

 

[SlaterB]

ich meine: wenn ein spezielles Objekt/ Klasse für die Suche, wie von mir genannt,
dann müssen dorthin die Netz-Daten, die bisher ja irgendwo vorhanden sind, übertragen werden,
damit auch auch als Instanzattribute verfügbar

 

[Luk10]

Achso. Nun gut ich denke ich nehme der Einfachheit halber, gleich die Klasse Graph, in der sich auch die Tiefensuche befindet.

-Luk10-