难以实现 BFS 以遍历图

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

我正在绞尽脑汁设计一个 BFS 算法来遍历给定起始位置和结束位置的图形。

我的最佳尝试确实产生了一系列动作，但不是最短的。

boolean[] pass = new boolean[9]; //if a move has been done, don't redo it
int s = 0; //starting position
int e = 2; //ending position
int[][] matrix; //the adjacency matrix previous defined

public List<Integer> BFS(int[][] matrix, int s) {
    List<Integer> paths = new LinkedList();
    List<Integer> shortest = new LinkedList();
    pass[s] = true; //starting position has been indexed
    paths.add(0,s); //insert part of path to front of list
    while (paths.isEmpty() == false) {
        int element = paths.get(0); //peek at first element
        shortest.add(element); //add it to shortest path
        int node = paths.remove(0); //remove from path
        if (element == e) { //if we've reached the end
            return shortest; //hopefully found shortest path
        } else {
            for (int i = 0; i < 9; i++) {
                //if adjacent element hasn't been indexed
                if (pass[i] == false && matrix[node][i] == 1) {
                    pass[i] = true;
                    paths.add(0,i);
                }
            }
        }
    }
    return null;
}

打印返回的列表产生：

[0, 3, 6, 4, 5, 8, 2]

当实际结果应该是：

[0, 3, 4, 5, 2]

在我看来，它所走的道路是这样的：

[0, 3, 6, backtrack to 3, 4, 5, 8, backtrack to 5, 2]

我的算法有什么问题？如何找到给定起点和终点的最短路径？

Here 一个 IDE 来说明。

Answer 1

您没有正确提取最短路径。您正在将您处理的每个个节点添加到最短路径。

如果你想使用BFS来寻找最短路径，你必须通过存储"back edges"来跟踪到每个中间节点的最短路径，只有最后你才能把它们放在一起找到最短路径。

对于您添加到队列中的每个节点，将使您到达该节点的节点存储为 "back edge":

if (pass[i] == false && matrix[node][i] == 1) {
    pass[i] = true;
    paths.add(0,i);

    // Add this:
    back[i] = node;
}

然后，一旦您的遍历完成，您可以使用这些引用通过从结束节点向后 "back edges" 查找完整路径。它将引导您（向后）到最短路径上的起始节点：

int node = e;
while (node != s) {
    shortest.add(0, node);
    node = back[node];
}
shortest.add(0, s);

更新:

感谢您的评论，我才意识到您的代码还有一个问题。您正在将新节点添加到列表的前面并从前面处理它们。所以你实际上有一个堆栈，而不是一个队列。这使您的算法有效地成为深度优先搜索 (DFS) 而不是广度优先搜索 (BFS)。 DFS 会给你一条从 s 到 e 的正确路径，但不一定是最短的路径。

为了将您的列表 paths（最好命名为 queue，顺便说一下）作为队列而不是堆栈，您必须从两端读取和写入，例如添加到后面（而不是前面）更改列表添加行

paths.add(0, i);

至

paths.add(i);

Answer 2

您的实施中的 shortest 数组与您想象的不同。它只是找到的所有顶点的列表，而不是最短路径，因为（如您所知）BFS 有时必须遵循不通向目标顶点的路径。

你需要做的是为每个顶点 v 存储它的 "parent" — 你从那里得到的顶点 v:

       if (pass[i] == false && matrix[node][i] == 1) {
            pass[i] = true;
            parent[i] = node;
            paths.add(0,i);
       }

然后在主 BFS 循环之后，您使用存储在 parent:

中的链接从目标顶点返回到源

// pseudocode
cur = e;
while cur != s
    answer.add_at_end(cur)
    cur = parent[cur];

难以实现 BFS 以遍历图

Difficulty implementing BFS for traversal of graph

java

algorithm

search

graph-theory

adjacency-matrix