java - 邻接矩阵 : premature ending of search, 上的广度优先算法返回大小为 1 的队列？

Question

adj 是一个邻接矩阵:

0 0 0 1 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 
0 0 0 0 0 1 0 0 0 
1 0 0 0 1 0 1 0 0 
0 0 0 1 0 1 0 0 0 
0 0 1 0 1 0 0 0 1 
0 0 0 1 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 
0 0 0 0 0 1 0 0 0 

adj 为下面的迷宫映射邻接关系(元素 # 在旁边):

S X E | 0 1 2
O O O | 3 4 5
O X O | 6 7 8

我正在使用邻接矩阵遍历迷宫中的元素。这是遍历矩阵的广度优先搜索算法。

queue Q = new queue();
boolean[] visited = new boolean[];
int num = 9; //number of elements
int begin = 0; //begin point as defined 'S'
int end = 2; //end point as defined 'E'
private queue BFS(int[][] adj, int begin) {
    visited[begin] = true;
    Q.enqueue(begin);
    while (!Q.isEmpty()) {
        int element = Q.dequeue();
        int temp = element;
        while (temp <= num) {
            if ((!visited[temp]) && (adj[element][temp] == 1)) {
                if (temp == end) {
                    return Q;
                }
                Q.enqueue(temp);
                visited[temp] = true;
            }
            temp++;
        }
    }
    return Q;
}

执行 BFS() 返回 size() 1 的队列。具体来说，队列仅包含 begin(在本例中为 0)。该算法应生成一个 [0, 3, 4, 5, 2] 队列。在第一个 while() 打开之后插入一个 System.out.println("blah") 显示它只迭代一次。

为什么我的算法会提前停止？我怎样才能调整它以获得我想要的输出？我的目标是设计一种算法，在这种情况下找到“0”和“2”之间可能的最短路径。

Answer 1

你在第一次迭代时遇到条件 temp == end 因为你的 temp 从 0 开始，然后它是 1 没有插入元素到队列(因为它不与 0 相邻)，然后它是 2 没有插入，在这里，在条件 temp == end(均等于 2)下，您返回仅包含 begin 的 Q，因为尚未插入任何内容。所以你只有一次外循环迭代和三次内循环迭代。

我建议进行以下修改

queue Q = new queue();
boolean[] visited = new boolean[];
int num = 9; //number of elements
int begin = 0; //begin point as defined 'S'
int end = 2; //end point as defined 'E'
private void BFS(int[][] adj, int begin) {
    visited[begin] = true;
    Q.enqueue(begin);
    while (!Q.isEmpty()) {
        int element = Q.dequeue();
        if (element == end) {
            return Q;
        }
        int temp = 0;
        while (temp < num) {
            if ((!visited[temp]) && (adj[element][temp] == 1)) {
                Q.enqueue(temp);
                visited[temp] = true;
            }
            temp++;
        }
    }
    return Q;
}