充分利用鄰接表節點，而穿越深度優先搜索 - Java的

Question

我想通過我的我的DFS的堆棧遍歷時儘可能快地得到這個代碼運行當前的輸入文件是像這樣：

0 2 
2 1 
1 4 
4 5 
5 6 
10 8 
8 9 
9 6 
7 6 
3 4 
0 1 
3 9 
0 4 

我的Maze課程將把這些數字聯繫在一起併爲我創建一個圖表。圖創建後，我的DFS類遍歷遍歷，給出提交的.txt文件的一個或所有解決方案。我最近更改了我的Maze類，因爲它可以更有效地運行，但是被拋出的錯誤和數據解析到我的輸出DFS。我的新Maze類如下：

import java.io.*; 
import java.util.*; 

public class Maze { 

    private final Map<Integer, Set<Integer>> adjList = new HashMap<>(); 

    /** 
    * The main constructor that takes a String for reading maze file. 
    * 
    * @param file 
    */ 
    public Maze(File file) throws FileNotFoundException { 
     try (Scanner scan = new Scanner(file)) { 
      while (scan.hasNextInt()) { 
       int node1 = scan.nextInt(); 
       int node2 = scan.nextInt(); 
       this.connect(node1, node2); 
       this.connect(node2, node1); 
      } 
     } 
    } 

    /** 
    * Makes a unidirectional connection from node1 to node2. 
    */ 
    private void connect(int node1, int node2) { 
     if (!this.adjList.containsKey(node1)) { 
      this.adjList.put(node1, new HashSet<Integer>()); 
     } 
     this.adjList.get(node1).add(node2); 
    } 

    /** 
    * Returns a human-readable description of the adjacency lists. 
    */ 
    public String toString() { 
     StringBuilder s = new StringBuilder(); 
     for (Map.Entry<Integer, Set<Integer>> adj : this.adjList.entrySet()) { 
      int from = adj.getKey(); 
      Set<Integer> to = adj.getValue(); 
      s.append(from).append(" connected to ").append(to).append('\n'); 
     } 
     return s.toString(); 
    } 

    /** 
    * Returns the set of nodes connected to a particular node. 
    * 
    * @param node - the node whose neighbors should be fetched 
    */ 
    public Iterable<Integer> getadjList(int node) { 
     return Collections.unmodifiableSet(adjList.get(node)); 
    } 

    /** 
    * Demonstration of file reading. 
    */ 
    public static void main(String[] args) throws FileNotFoundException { 
     System.err.print("Enter File: "); 
     Scanner scanFile = new Scanner(System.in); 
     String file = scanFile.nextLine(); 
     Maze m = new Maze(new File(file)); 
     System.out.println(m); 
    } 

} 

我的問題是我怎麼拉當前節點到我DFS類我的圖，我已經試過喜歡的幾件事情：

maze.adjList.getNode() 
maze.getadjList.get(node) 
maze.adjList.get(node) 

編輯： ：DFS類如下，如果有幫助：

import java.io.*; 
import java.util.*; 

public class DFS { 
    //starting node, the route to the next node, has node been visited 
    private int startNode; 
    private int goalNode; 
    private int[] route; 
    private boolean[] visited; 


    // 2 main arguments - Maze File & user input 
    public DFS(Maze maze, int input) { 
     int startNode = 0; 
     int goalNode = 1; 
     route = new int[maze.adjList.getNode()]; 
     visited = new boolean[maze.adjList.getNode()]; 
     //Takes user's input and runs desired function 
     if(input == 1){ 
     findOne(maze, startNode, goalNode); 
     } 
     else if (input == 2){ 
     findAll(maze, startNode, goalNode); 
     } 
     else { 
      System.out.println("input invalid. No Solution Returned"); 
     } 
    } 



    //Put path to goal in the stack 
    public Stack<Integer> route(int toGoalNode) { 
     if (!visited[toGoalNode]) { 
      return null; 
     } 
     Stack<Integer> pathStack = new Stack<Integer>(); 
     for (int routeGoalNode = toGoalNode; routeGoalNode != startNode; routeGoalNode = route[routeGoalNode]) { 
      pathStack.push(routeGoalNode); 
     } 
     pathStack.push(startNode); 
     reverseStack(pathStack); 
     return pathStack; 
    } 

    //Reverse the stack 
    public void reverseStack(Stack<Integer> stackToBeReverse) { 

     if (stackToBeReverse.isEmpty()) { 
      return; 
     } 

     int bottom = popBottomStack(stackToBeReverse); 
     reverseStack(stackToBeReverse); 
     stackToBeReverse.push(bottom); 
    } 

    //Pop the bottom of the stack 
    private int popBottomStack(Stack<Integer> stackToBeReverse) { 
     int popTopStack = stackToBeReverse.pop(); 
     if (stackToBeReverse.isEmpty()) { 
      return popTopStack; 
     } else { 
      int bottomStack = popBottomStack(stackToBeReverse); 
      stackToBeReverse.push(popTopStack); 
      return bottomStack; 
     } 
    } 

    //performs DFS and unsets visited to give the result of all paths 
    private void findAll(Maze maze, int node, int goal) { 
     visited[node] = true; 
     if(node == goal) { 
      printPath(goal); 
     } else { 
      for (int con : maze.getadjList(node)) { 
       if (!visited[con]) { 
        route[con] = node; 
        findAll(maze, con, goal); 
       } 
      } 
     } 
     visited[node] = false; 
    } 

    //performs DFS and maintains visited marker giving only one path 
    private void findOne(Maze maze, int node, int goal) { 
      visited[node] = true; 
      for (int con : maze.getadjList(node)) { 
       if (!visited[con]) { 
        route[con] = node; 
        findOne(maze, con, goal); 
       } 
      } 
     } 

    //Traverse the connections to the goal and print the path taken 
    public void printPath(int toGoal) { 
     int goalNode = 1; 
     if (visited[toGoal]) { 
      System.out.println("Completed Path: "); 
      for (int t : route(toGoal)) { 
       if (t == toGoal) { 
        System.out.print(t); 
       } else { 
        System.out.print(t + " -> "); 
       } 
      } 
      System.out.println(); 
     } 
    } 


    public static void main(String[] args){ 
     Scanner scanFile = new Scanner(System.in); 
     int goalNode = 1; 
     System.out.print("Enter maze file: "); 
     String file = scanFile.nextLine(); 
     Maze maze = new Maze(new File(file)); 
     Scanner scanInt = new Scanner(System.in); 
     System.out.print("Enter desired feedback (1 = one soultion, 2 = all): "); 
     int input = scanInt.nextInt(); 
     maze.toString(); 
     System.out.println(maze);   
     DFS dfs = new DFS(maze, input); 
     dfs.printPath(goalNode); 
     } 

} 

Answer 1

由於鄰接表adjList是一個私有成員，你會寫在的方法用於將該列表的元素暴露給DFS。

public Set<Integer> getNode(int node) { 
    return Collections.unmodifiableSet(adjList.get(node)); 
} 

你似乎需要節點也數量，這將是類似的另一種方法：

public int getNumberOfNodes() { 
    return adjList.size(); 
}