DFS java尋路問題

我正在開發一種搜索算法來查找圖中的路徑。在這個算法中，我需要找到一個無向圖的所有路徑，而不是加權圖，它們只能通過一次圖形連接。目前，我的prgoram正在做的是找到通過每個節點只有一次的所有路徑。我需要連接而不是節點。DFS java尋路問題

這裏是我的代碼：

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

正在通過各節點不會超過一次的程序。我需要幫助轉換我的程序，每次只連接一次，而不是每次只連接一次。

（我對我的英語對不起，我不是本地人）

來源

2012-03-21 Maritza Guerreiro

如果你願意做一些重寫，我想這樣的問題是在面向對象的方式更清晰地表達。

您可以從Node和Edge實例中構建鏈接圖，從而允許您在遍歷圖時標記訪問邊。

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

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

來源

2012-03-22 05:23:24 ulmangt

DFS java尋路問題

回答

相關問題