邻接矩阵的广度优先算法：过早结束搜索，returns 大小为 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() returns 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）下，您是 return Q，它仅包含 begin，因为尚未插入任何内容。所以你只有一次外循环迭代和三次内循环迭代。

我建议进行以下修改

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;
}

邻接矩阵的广度优先算法：过早结束搜索，returns 大小为 1 的队列？

Breadth-first algorithm on adjacency matrix: premature ending of search, returns queue of size 1?

java

algorithm

graph

breadth-first-search

adjacency-matrix