DFS Javaパスファインディングの問題

Question

私は、グラフ内のパスを見つけるための検索アルゴリズムを開発しています。このアルゴリズムでは、各グラフ接続を一度だけ通過する無向グラフではなく、すべての経路を見つける必要があります。 現在、私のprgoramがやっていることは、各ノードを一度だけ通過するすべてのパスを見つけることです。私は、ノードではなく接続が必要です。ここで

が私のコードです：

import java.util.*; 

public class dfs { 

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

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

    public int getNumLinks(){ 
     return 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 adj) { 
     LinkedHashSet<Integer> adjacente = map.get(adj); 
     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; 

    dfs mapa = new dfs(startNode, numLinks); 

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

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

    Iterator it = map.entrySet().iterator(); 
    while (it.hasNext()) { 
     Map.Entry pairs = (Map.Entry)it.next(); 
     currentNode = (Integer) pairs.getKey(); 

     mapa.findAllPaths(mapa, visited, paths, currentNode); 
    } 
} 

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

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

     LinkedList<Integer> nodes = mapa.adjacentNodes(currentNode); 

     for (Integer node : nodes) { 
      List<Integer> temp = new ArrayList<Integer>(); 
      temp.addAll(visited); 
      temp.add(node); 
      System.out.println("temp:" + temp); 

      findAllPaths(mapa, temp, paths, node); 
     } 
    } 
    else { 
     LinkedList<Integer> nodes = mapa.adjacentNodes(currentNode); 
     System.out.println("currentNode:" + currentNode); 

     List<Integer> inseridos = new ArrayList<Integer>(); 

     for (Integer node : nodes) { 
      if (visited.contains(node)) { 
       continue; 
      } 
      List<Integer> temp = new ArrayList<Integer>(); 
      inseridos.add(currentNode); 
      temp.addAll(visited); 
      System.out.println("visited:" + visited); 

      temp.add(node); 

      findAllPaths(mapa, temp, paths, node); 
     } 
    } 
} 
} 

今、私は次のコードを考える：

if (visited.contains(node)) { 
    continue; 
} 

は、プログラムが複数回、各ノードを経由していないことを行っています。 私のプログラムを変えるのを助ける必要があるのは、各接続を1度だけ通過することです。

（私はネイティブではないよ、私の英語について申し訳ありません）

Answer 1

あなたには、いくつかの書き換えを行うために喜んでいる場合は、私はこの種の問題は、よりきれいにOOの様式で発現されると思います。

NodeとEdgeのインスタンスからリンクされたグラフを作成して、グラフを横断するときに訪問エッジをマークすることができます。

class Node 
{ 
    List<Edge> adjacentEdges; 
    boolean isVisited; 
} 

class Edge 
{ 
    Node node1; 
    Node node2; 
    boolean isVisited; 
}