Tiefe erste Suche rekursiv vom ersten Knoten zum letzten Java

Question

Ich habe eine Zuweisung, in der wir ein Array von Vertices haben, jeder Vertex hat eine Array-Liste mit benachbarten Vertices. Das Ziel besteht darin, einen Pfad vom ersten zum letzten rekursiv zu finden. Sobald der Tiefensuchalgorithmus den Zielknoten erreicht, fügt er ihn dem Lösungspfad hinzu (doppelt verkettete Liste), und fügt dann alle Scheitelpunkte auf dem direkten Pfad rekursiv zum Quellknoten zurück. hier ist mein Code so weit (statt solutionPath.add im nur Druck auf die Konsole zu sehen, was mit dem Pfad zu der verknüpften Liste hinzugefügt werden würde)

private DoublyLinkedList<Vertex> dfs(int firstRoom, int lastRoom, boolean[] 
visited){ 
System.out.println(firstRoom); 
if(visited[lastRoom]== true){ 


    return pathSolution; 


} 

Iterator<Edge> n = rooms[firstRoom].getEdgesIterator(); 
while(n.hasNext()){ 
    int e= n.next().getAdjacentVertex(); 

    if(!visited[e]){ 
     visited[e]=true; 
     return dfs(e, lastRoom, visited); 

    } 


} 


return pathSolution; 


} 

Answer 1

Sie können es wie folgt aus:

List dfs(v): 
    visited[v] = True 
    if v == last_vertex: 
     // If v is the last vertex, we can simply return the list containing it 
     return [last_vertex] 
    for u in neighbors of v: 
     if not visited[u]: 
      list_from_u = dfs(u) 
      // If the list is non-empty, last_vertex is reachable from v 
      // and the list contains a valid path to it 
      // So we just need to add v to the front of the list and return 
      // the result. Otherwise, there's no path from u to the last_vertex 
      // so we do nothing right here and keep looking 
      if not list_from_u.empty(): 
        list_from_u.prepend(v) 
        return list_from_u 
    // There're was no path to the last_vertex, so we return an empty list 
    // to indicate it  
    return []