我有一个迷宫搜索算法，并没有在终点停止，而且还在打印不需要的节点

Question

我将不胜感激任何帮助...

我有 2 种迷宫搜索算法，分别是 DFS 和 BFS。起点设置为 0，终点设置为 1。节点放置在堆栈中并开始访问其邻居以查找指向 1 的路径。应擦除未参与 1 路径的节点，这不会发生。而且当路径找到目标 1 时，它不会停止。基本上测试迷宫路径应该是 0 5 4 1，而 BFS 给我 0 3 5 0 2 11 4 7 1 6 8 9 10 和DFS给我0，它启动，它永远不会找到任何东西。我认为问题可能出在printNode函数或访问的isVisited上。

以下是与这些问题相关的方法。提前感谢您的任何帮助。

import java.util.*;

public class Maze {

public Node startingNode;
public ArrayList<Node> nodes = new ArrayList<>();
public int[][] matrix = new int[100][100];

// to set starting node at 0 
public void setStartingNode(Node n) {
    this.startingNode = n;
}
public Node getStartingNode() {
    return this.startingNode;
}
public void addNode(int n) {
    nodes.add(new Node (n));
}
public void visited(int n1) {
    for(Node n2 : nodes) {
        if(n2.list == n1) {
             n2.visited = true;
        }
    } 
}
public boolean isVisited(int n1) {
    for(Node n2 : nodes) {
        if(n2.list == n1) {
            return n2.visited ;
        }
    }
    return false;
}
public Node getNode(int n) {
    for(Node n2 : nodes) {
        if(n2.list == n) {
            return n2;
        }
}
    return new Node(-1);
}
//TODO get the next unvisited node
public Node getNextNode(Node n) {
    int link = n.list;
    int i = 0;                      
    while (i<nodes.size()) {
        if(matrix[link][i] == 1 && isVisited(i) == false)
        {
            return (Node)getNode(i);
        }
        i++;
    }
    return null;
}

//algorithm uses queue and should find all paths
public void bfs() {
    Queue<Node> q=new LinkedList<Node>();
    q.add(this.startingNode);
    printNode(this.startingNode);
    startingNode.visited=true;
    while(!q.isEmpty())
    {
        Node n=(Node)q.remove();//
        Node child=null;//
        while((child=getNextNode(n))!=null)
        {
            child.visited=true;
            printNode(child);
            q.add(child);
        }
    }
    //Clear visited property of nodes
    clearNodes();
}
// algorithm uses stack and should find fastest solution
public void dfs() {

    Stack<Node> s=new Stack<Node>();
    s.push(this.startingNode);
    startingNode.visited=true;
    printNode(startingNode);
    while(!s.isEmpty())
    {
        Node n=(Node)s.peek();
        Node child=getNextNode(n);
        if(child!=null)
        {
            child.visited=true;
            printNode(child);
            s.push(child);
        }
        else
        {
            s.pop();
        }
    }
    //Clear visited property of nodes
    clearNodes();
}
private void clearNodes() {
    int j = 0;
    while (j < 0) {
        Node n = (Node)nodes.get(j);
        n.visited = false;
        j++;
    }
}
// to print nodes 
private void printNode(Node n) {
    System.out.print(n.list + " ");
}
}

以下是主要类

import java.util.*;
import java.io.*;
import javax.swing.*;
// C:UsersMannieDesktopmaze1.txt
// C:UsersMannieDesktopmaze2.txt
// C:UsersMannieDesktopmaze3.txt
public class Main {
public static void main(String args[]) throws IOException {
    String stringNode;
    File file = new File(JOptionPane.showInputDialog("Please enter file path"));
    ArrayList<String> nodes = new ArrayList<>();
    Maze maze = new Maze();
    maze.setStartingNode(new Node(0));
    // idea is to convert string into 2D arrays here removing substring " " using .split
    try {
        try (Scanner sc = new Scanner(new FileInputStream(file))) {
            while (sc.hasNextLine()) {
                stringNode = sc.nextLine();
                nodes.add(stringNode);
                String[] segment = stringNode.split(" ");
                //for (String val: ){
                    //the first time this loops the value will be 11, the second time it will be 3
                    //i have no idea what you 
                    int intNode1 = Integer.parseInt(segment[0]);
                    int intNode2 = Integer.parseInt(segment[1]);
                    //System.out.println(intNode);
                    maze.matrix[intNode1][intNode2] = 1;
                    maze.matrix[intNode2][intNode1] = 1;

            }
            // nodes
            for (int k=0;k<100;++k)
                maze.nodes.add(new Node(k));
        } 
        finally
        {
        }
    } catch (FileNotFoundException e) {
    }
    Iterator<String> i = nodes.iterator();
    while (i.hasNext()) {
        System.out.println(i.next());
    }

    // To print bfs results
    // also print the system clock time to time the algorithm using
    // System.nanoTime();
    maze.bfs();
    System.nanoTime();
    System.out.println();
    // To print dfs results
    // also print the system clock time to time the algorithm using
    // System.nanoTime();
    maze.dfs();
    System.nanoTime();
}
}

这是只通过节点的节点类

public class Node {
public int list;
public boolean visited = false;
public Node(int node) {
    this.list = node;
}
}

Answer 1

在你的代码中

public Node getNode(int n) {
    for(Node n2 : nodes) {
        if(n2.list == n) {
            return n2;
        }
    }
    return new Node(-1);
}

您返回的是new Node(-1);，而不是像您在此处预期的那样返回null：

while((child=getNextNode(n))!=null)
{
    child.visited=true;
    printNode(child);
    q.add(child);
}

这会导致打印错误的节点，并且不会停止。此代码取自bfs()，但也适用于dfs()。您应该改为返回null。