Grüße,
Ich habe einen Graphen mit, wie üblich, einer Knotenliste als
.
Nun habe ich folgende Aufgabe / Problem:
Ich soll eine
ausgeben, welche die Knoten eines möglichen Weges (Also nicht der kürzeste) von
bis
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:
P.S. Falls jemand "unschöne" englische Bezeichnungen auffallen, bitte bescheid geben
Danke,
-Luk-
Ich habe einen Graphen mit, wie üblich, einer Knotenliste als
Code:
Knoten[]
Nun habe ich folgende Aufgabe / Problem:
Ich soll eine
Code:
ArrayList<Knoten>
Code:
start_index
Code:
ziel_index
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:
Java:
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-