用DFS查找圖中的所有路徑

Question

早上好！

我正在開發一種算法來查找無向圖中的所有路徑。我目前正在使用帶回溯的DFS algortihm來嘗試這樣做。這是我現在的代碼：

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 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; 

    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(); 
     //System.out.println("Current Node:" + currentNode); 
     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); 
     //System.out.println("visited:" + visited); 

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

    } 

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

} 

} 

該程序在他的輸入接收整數。第一個是節點數量，第二個是鏈接數量，第三個是開始節點和結束音符，它們是相同的。所有後面的整數表示節點之間的連接。

問題是，該算法找到的所有路徑只訪問一次單個節點。我想要的是查找所有訪問每個連接的路徑的算法。 關於如何做到這一點的任何想法？

Answer 1

你正處在正確的軌道上 - 回溯是解決問題的好方法。

要獲得所有的路徑是「使用相同的邊緣只有一次」： 你findAllPaths()使用邊緣之後 - 從邊緣集[刪除這條邊的每個頂點的LinkedHashSet連接]中刪除它 - 以遞歸方式調用。

從遞歸返回後 - 不要忘記「清理環境」並將此邊添加回兩個頂點。

您需要確保在修改時不會遇到迭代集合的麻煩。 [你做不到 - 這樣做的結果是意外的] - 所以你可能需要發送LinkedHashSet的副本[沒有相關的邊緣] - 而不是原來的。