자바를 사용하여 그래프에서 경로 알고리즘 찾기

Question

학교 프로젝트를 위해 자바에서 검색 알고리즘을 구현해야합니다. 이 알고리즘에서는 방향없는 그래프에서 각 링크를 한 번만 통과하여 시작 노드에서 끝나는 경로를 찾아야합니다. 이 문제를 해결하기 위해 역 추적과 함께 DFS를 사용하려고하지만 구현하는 데 문제가 있습니다. 여기에 내 코드입니다 :

import java.util.*; 

public class Graph { 

    private Map<Integer, LinkedHashSet<Integer>> map = 
     new HashMap<Integer, LinkedHashSet<Integer>>(); 
    private int startNode; 
    private int numLinks; 



    public Graph(int startNode, int numLinks) { 
     super(); 
     this.startNode = startNode; 
     this.numLinks = numLinks; 
    } 

    public void addEdge(int source, int destiny) { 
     LinkedHashSet<Integer> adjacente = map.get(source); 
     if(adjacente==null) { 
      adjacente = new LinkedHashSet<Integer>(); 
      map.put(source, adjacente); 
     } 
     adjacente.add(destiny); 
    } 

    public void addLink(int source, int destiny) { 
     addEdge(source, destiny); 
     addEdge(destiny, source); 
    } 

    public LinkedList<Integer> adjacentNodes(int last) { 
     LinkedHashSet<Integer> adjacente = map.get(last); 
     System.out.println("adjacentes:" + adjacente); 
     if(adjacente==null) { 
      return new LinkedList<Integer>(); 
     } 
     return new LinkedList<Integer>(adjacente); 
    } 

public static void main(String[] args) { 

    Scanner input = new Scanner(System.in); 

    int numVertices = input.nextInt(); 
    int numLinks = input.nextInt(); 
    int startNode = input.nextInt(); 
    int endNode = startNode; 

    Graph mapa = new Graph(startNode, numLinks); 

    for(int i = 0; i<numLinks; i++){ 
     mapa.addLink(input.nextInt(), input.nextInt()); 

    } 

    List<ArrayList<Integer>> paths = new ArrayList<ArrayList<Integer>>(); 
    Integer currentNode = startNode; 
    List<Integer> visited = new ArrayList<Integer>(); 
    visited.add(startNode); 
    mapa.findAllPaths(mapa, visited, paths, currentNode); 

    for(ArrayList<Integer> path : paths){ 
     for (Integer node : path) { 
      System.out.print(node); 
      System.out.print(" "); 
     } 
     System.out.println(); 
    } 

} 

private void findAllPaths(Graph mapa, List<Integer> visited, 
     List<ArrayList<Integer>> paths, Integer currentNode) { 


    if (currentNode.equals(startNode)) { 
     paths.add(new ArrayList<Integer>(visited)); 
     return; 
    } 

    else { 
     LinkedList<Integer> nodes = mapa.adjacentNodes(currentNode);  
     for (Integer node : nodes) { 
      if (visited.contains(node)) { 
       continue; 
      } 
      List<Integer> temp = new ArrayList<Integer>(); 
      temp.addAll(visited); 
      temp.add(node);   
      findAllPaths(mapa, temp, paths, node); 
     } 
    } 

} 

} 

이 프로그램은 첫 번째 노드의 수는 자신의 입력에 정수를받을 예정이다, 두 번째는 링크의 수는 느릅 나무는 (세 번째는 시작 노드이며, 또한 끝 노드), 뒤 따르는 모든 정수는 노드 사이의 링크를 나타냅니다.

결국 목표는 정수가있는 한 줄을 인쇄하는 것입니다. 이 정수는 각 노드를 방문하여 경로를 완료하는 순서를 나타냅니다. 현재 테스트 중이므로 첫 번째 노드를 나타내는 단일 정수 만 인쇄합니다.

내 문제는 그래프를 채우거나 인접 목록을 채우는 것입니다. 누군가 나를 도울 수 있습니까?

Answer 1

mapa.findAllPaths(mapa, visited, paths, currentNode);에 전화 할 때 실제로 모든 경로를 찾지 못하는 것이 문제입니다. 당신은 하나 개의 경로 (즉, 현재 노드)를 발견하고 당신은 반환 :

private void findAllPaths(Graph mapa, List<Integer> visited, 
     List<ArrayList<Integer>> paths, Integer currentNode) { 

    if (currentNode.equals(startNode)) { 
     paths.add(new ArrayList<Integer>(visited)); 
     return;// <--- WRONG!!! 
    } else { 
     // The else is never executed! 
    } 
} 

당신은 루프를하거나 모든 경로를 찾을 때까지 반복적으로 findAllPaths를 호출해야 하나.

Answer 2

당신이 currentNode.equals(startNode) 진실되고 리드 마지막 인수로 startNode을 전달하는 findAllPaths 방법합니다 (currentNode)를 호출하고 실행됩니다 방법의 등 만 일부로서 처음입니다

paths.add(new ArrayList<Integer>(visited)); 
return; 

본질적으로 경로에 첫 번째 노드 만 추가하면 알고리즘이 완료되므로 항상 시작 노드 인 단일 정수가 인쇄됩니다.