소스에서 대상까지의 경로를 찾는 반복 DFS

Question

경로를 찾기 위해 DFS 구현을 디버깅하는 데 도움을 주셔서 감사합니다. 내 구현은 일반적으로 잘 작동하지만 일정한 경우에는 알고리즘에 의해 방문되는 결과에 여분의 노드가 추가되지만 결과 목록의 다음 노드까지 경로가 존재하지 않기 때문에 솔루션 내에 포함되어서는 안됩니다. 이 문제는 Result.add (nextNode)의 위치에 의해 발생하지만이 버그를 해결할 수 없었습니다.

문제의 예가 아래에 첨부되어 있습니다 (임의의 가중치). 따라서 알고리즘은 4에서 1까지의 가장자리가 없더라도 [0 2 4 1 3 5]를 결과로 반환합니다.

Example

사람은 4와 같은 노드가 결과를하시기 바랍니다 추가되지 않도록 내 코드를 수정하는 방법을 제안 할 수 있습니다? result 목록에 당신이 visited 목록에 추가 할 때마다 노드를 추가

public static ArrayList<Integer> pathDFS(Integer source, Integer destination, WeightedGraph graph) { 
      ArrayList<Integer> Result = new ArrayList<Integer>(); 
      ArrayList<Integer> Visited = new ArrayList<Integer>(); 
      Stack<Integer> s = new Stack<>(); 
      s.push(source); 
      Visited.add(source); 
      while (!s.isEmpty()) { 
       Integer v = s.pop(); 
        for (int nextNode : getAdjacentNodes(v, graph)) { 
         if (!Visited.contains(nextNode)) { 
          s.push(nextNode); 
          Visited.add(nextNode); 
          **Result.add(nextNode);** 
          if (nextNode == destination) 
           return Result; 
        } 
       } 
      } 
      return Result; 
     } 

Answer 1

방문 노드 세트는 반드시 바로 경로를 포함하지 않습니다 (분명히 잘못된 것입니다. 그것은뿐만 아니라, 다른 노드의 무리를 가질 수 있습니다 하나).

수정하려면 parent 목록을 만들어 각 노드의 부모를 저장하고 새 노드를 발견 할 때 채우십시오. 이렇게하면 경로를 재구성하기 위해 소스에 대한 부모 링크로 대상 노드에서 이동해야합니다.