java - 使用 DFS 将参数传递给我的 main 时出现问题 - 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 看起来像这样。

import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;
import java.util.Stack;

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


    // 2 main arguments - Maze File & user input
    public DFS(Maze maze, int inputInt) {
        int startNode = 0;
        int goalNode = 1;
        route = new int[maze.node];
        visited = new boolean[maze.node];
        //Takes user's input and runs desired function
        if(inputInt == 1){
        findOne(maze, startNode, goalNode);
        }
        else if (inputInt == 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) throws FileNotFoundException {
        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 inputInt = scanInt.nextInt();
       // maze.toString();
        System.out.println(maze);           
        DFS dfs = new DFS(maze, inputInt);
        dfs.printPath(goalNode);
        }

}

我已经研究了一段时间，但无法弄清楚为什么要解析和使用数据。我在这里和那里改变了一些东西，但抛出了更多的错误。他们特别说

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 0
    at DFS.findOne(DFS.java:90)
    at DFS.<init>(DFS.java:22)
    at DFS.main(DFS.java:127)

引用代码行:

visited[node] = true;
findOne(maze, startNode, goalNode);
DFS dfs = new DFS(maze, inputInt);

现在基本上我相信没有任何争论被通过，如果有人能指出问题并帮助我解决问题，我将不胜感激。再次感谢

编辑::Maze 类的旧版本

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



public class Maze {

    static Set<Integer> Nodes = new HashSet<Integer>();
    List<Integer>[] conList;
    int node; //declaring value for my nodes.
    int con; // declaring a connection


    //Constructor takes an int parameter to read through the list of corresponding nodes
    Maze(int node) {
        this.node = node;
        this.con = 0;
        conList = (List<Integer>[]) new List[node];
        for (int index = 0; index < node; index++) {
            conList[index] = new LinkedList<Integer>();
        }
    }

    //Constructor that takes a String of the maze file 
    public Maze(String mazeFile) {
        this(nodeSize(mazeFile));
        Scanner scan;
        try {
            //Creates a scanner for reading the file and loops through linking the nodes to their connections.
            scan = new Scanner(new File(mazeFile));

            while (scan.hasNextInt()) {
                int firstNode = scan.nextInt();
                int secondNode = scan.nextInt();
                addCon(firstNode, secondNode);
            }
        } catch (FileNotFoundException ex) {
            System.out.println("File Not Found.");
        }
    }


    /*Takes String parameter which is the name of the maze file. 
     * Method designed to return the the size of the set of nodes
     */
    public static int nodeSize(String mazeFile) {
        Scanner scanNodeSize;
        try {
            scanNodeSize = new Scanner(new File(mazeFile));
          //while scan has more int's left repeat.
            while (scanNodeSize.hasNextInt()) { 
                int firstNode = scanNodeSize.nextInt();
                int secondNode = scanNodeSize.nextInt();
                Nodes.add(firstNode);
                Nodes.add(secondNode);
            }
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        }
        return Nodes.size();
    }

    //Method designed to connect the first and second nodes 
    private void addCon(int firstNode, int secondNode) {
        con++; 
        conList[firstNode].add(secondNode);
        conList[secondNode].add(firstNode);
    }

    //outputs the nodes and their connection's (#remove later?)
    public void print() {

        for (int n = 0; n < node; n++) {
            System.out.print(n + " connected to ");
            for (int w : conList[n]) {
                System.out.print(w + " ");
            }
            System.out.println();
        }
    }


    //method returns a list, enabling nodes to be easily accessible.
    public Iterable<Integer> getconList(int nodes) {
        return conList[nodes];
    }

}

Answer 1

您在 0 处遇到索引越界异常。这应该会让您相信数组尚未正确初始化。您使用 maze.node 初始化访问[]数组，但是在您的代码中我们看不到该节点变量所在的位置。如果您希望 maze.node 能够运行，您需要为 maze.node 指定一个适当的值。

*编辑 - 现在我的上述答案不再适用，因为我们有您之前的 Maze 类，它解释了为什么代码无法运行。

当前状态下的代码存在很多问题，因此我将尝试在这里为您提供一些指导:

创建迷宫的新方法是从文件中读取并连接 2 个点并将它们存储在 map 中。问题是你不能只获取下一个元素，因为你必须拥有获取该元素的 key 。要解决此问题，您应该使用不同的数据结构。

    public DFS(Maze maze, int inputInt) {
        int startNode = 0;
        int goalNode = 1;
        route = new int[maze.node]; //!!! maze.node isn't a thing anymore
        visited = new boolean[maze.node]; //!!! maze.node isn't a thing anymore

您可以看到您正在尝试访问 maze.node，它曾经是 Maze 的变量。现在不再是了。您需要找到一种从迷宫获取节点的新方法。为此，您需要以不同的方式从数据结构中获取节点:

        public DFS(Maze maze, int inputInt) {
        int startNode = 0;
        int goalNode = 1;
        route = new int[maze.adjList.getNode()];
        visited = new boolean[maze.adjList.getNode()]; 

对于邻接列表，您有很多不同数据结构的选项，但如下所示:

http://theoryofprogramming.com/adjacency-list-in-java/

将为您提供一个不错的起点。