Рекурсивный DFS с неработающим ходом

Question

У меня есть класс State и он содержит ArrayList ребер. Я пытаюсь вычислить путь из одного состояния в другое с помощью DFS.

public class State{ 
    private String name; 
    private ArrayList<State> edges; 

    public ArrayList<State> depth-first-search(State start, State goal, ArrayList<State> path){ 
     if (start.equals(goal)) { 
      path.add(start); 
      return path; 
     } 
     else 
     { 
      start.setFound(true); 
      for (State state: start.getEdges()) 
      { 
       if (!state.found) 
       { 
        //we haven't looked at this state, let's look at it 
        path.add(state); 
        path = depth-first-search(state, goal, path); 
       } 
      } 
      return path; 
     } 

Существует проблема с получением пути состояний, но я не уверен, что именно. Он просто продолжает смотреть на состояния даже после того, как мы нашли свою цель.

Answer 1

public List<State> dfs(State start, State goal) { 
    List<State> list = new ArrayList<State>(); 
    if (dfsImpl(start, goal, list)) 
     return list; 
    else 
     return null; 
} 

private boolean dfsImpl(State start, State goal, ArrayList<State> path) { 
     if (start.equals(goal)){ 
      path.add(start); 
      return true; 
     } 
     else{ 
      start.setFound(true); 
      for (State state: state.getEdges()){ 
       if (!state.found){ 
        //we haven't looked at this state, let's look at it 
        path.add(state); 
        if (DFS(state, goal, path)) 
         return true; 
       } 
      } 
     return false; 
    }