java - 从 map 获取我的 DFS 遍历的 getNode - 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 类(class)会将数字联系在一起并为我创建一个图表。创建图形后，我的 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 算法。我的 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);
        }

}

我希望实现一个 getNode() 来针对我的 adjList 引用我在 DFS 中的行:

route = new int[maze.adjList.getNode()];
visited = new boolean[maze.adjList.getNode()];

谢谢。

Answer 1

你只需要将数组初始化为合适的大小

    route = new int[maze.adjList.size()];
    visited = new boolean[maze.adjList.size()];