그래프에서 DFS를 실행하는 데 문제가 있습니다.

Question

노드에 (String from, String to int time) 노드가 있습니다. HashMap을 지정하면 (자), key는 String이며, value는 from의 Node의리스트입니다.

주어진 시작점 (문자열 시작)에서 끝점 (문자열 끝)까지 가능한 모든 경로를 찾기위한 함수를 작성하고 싶습니다. dfs 함수를 작성하려고했지만 결과 세트가 하나만 반환됩니다. 누구든지 도울 수 있니? 노드의 목록

목록 목록의 결과 목록 : 키는 다음과 같습니다 일시적 목록

의 HashMap가> 그래프는 현재 노드를 기록

목록> 입술 INT 시간에 문자열에서 문자열 : 노드

• 모든 값에서 값
• CUR에서와 같은 노드 목록은 : 시작 값으로 시작하고 각 DFS에게
• 단부 변경할 : 방문 대상

• 을 : 세트가 난 당신이 Set JavaDoc 보면 버그가 라인

  visited.remove(visited.size()-1); 
  

  에 있음을 의심

  private static void dfs(res, list,HashMap<String, List<Node>> graph,String cur, String end, visited){ 
      if(cur.equals(end)) { 
       res.add(new ArrayList<Node>(list)); 
       return; 
      } 
      for(Node n : graph.get(cur)) { 
       if (visited.contains(n.to)) continue; 
       list.add(n); 
       visited.add(n.to); 
       dfs(res, list, graph, n.to, end, visited); 
       list.remove(list.size()-1); 
       visited.remove(visited.size()-1); 
      } 
  } 
  

Answer 1

로/방문 기록하려면, 당신은 유일한 remove 방법 인 것을 알 수 있습니다 boolean remove(Object o)이고 인덱스 별 제거는 List과 같습니다. 그래서 그 라인은 효과적으로 (자동 권투 덕분에) :

visited.remove(Integer.valueOf(visited.size()-1)); 

분명히 당신이 원하는대로 아무것도 제거하지 않습니다. 대신 방문한 노드를 값으로 제거하십시오.

visited.remove(n.to);