路径未按预期工作的递归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;
    }