グラフを使ってパスアルゴリズムを見つける

Question

学校プロジェクトのためにJavaで検索アルゴリズムを実装する必要があります。このアルゴリズムでは、無向グラフで、各リンクを1回だけ通過して開始ノードで終了するパスを見つける必要があります。私は、この問題を解決するためにバックトラックと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); 
     } 
    } 

} 

} 

プログラムは最初のものは、二つ目は、第三は、開始ノードリンク数のノードの数ですされて彼の入力、上の整数を受け取ることになっている（ウィッヒがありますエンドノードでもある）、後に来るすべての整数はノード間のリンクを表します。

目的は、最終的に整数で1行を出力することです。この整数は、各ノードを訪問してパスを完成させる順序を表します。現在のテストでは、最初のノードを表す単一の整数だけが出力されます。

私の問題は、グラフにデータを入力して隣接リストにデータを入力することだと思います。誰かが私を助けることができますか？

Answer 1

mapa.findAllPaths(mapa, visited, paths, currentNode);を呼び出すと、実際にはすべてのパスが見つからないという問題があります。 1つのだけのパス（すなわち、現在のノード）を見つけ、あなたは返す：

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法（現ノード）を呼び出すと実行されます方法のように唯一の一環として最初の時間は次のとおりです。

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

本質的に、最初のノードをパスに追加するだけでアルゴリズムが終了するので、常に開始ノードという単一の整数が出力されます。