广度优先搜索无法找到确实存在的目的地

Question

所以我一直在研究 Breadth First Search 以获得给定起始和结束节点的路径。但是在某些情况下，它似乎会失败并且无法获得路径，我知道这是可能的，因为深度优先搜索和目视检查表明它应该存在。

我有一个邻接矩阵：

     1       2       3       4       5       6       7       8

 1   0       20      25      20      0       0       0       0
 2   20      0       5       0       30      0       0       0
 3   25      5       0       13      8       21      0       0
 4   20      0       13      0       0       17      0       0
 5   0       30      8       0       0       33      0       0
 6   0       0       21      17      33      0       0       0
 7   0       0       0       0       0       0       0       10
 8   0       0       0       0       0       0       10      0

其中有如下图表：

这是我的功能：

void Network::BFS(int src, int dest, vector<bool>& visited, vector<int>& path) {
    // The Queue is the core for the BFS.
    queue<int> Queue;
    // Mark current node as visited.
    visited[src] = true;
    Queue.push(src);
    // While queue is not empty.
    while (!Queue.empty()) {
        // Add node to path.
        // Check if we have found the destination yet or not, if we have we do one last push to path and we're done!
        if (Queue.front() == dest) {
            return;
        }
        int top = Queue.front();
        path.push_back(Queue.front());
        // Pop off front.
        Queue.pop();
        // Iterate and process all none visited nodes.
        for (int node = 0; node < amountOfNodes; node++) {
            // Check if it is not visited already.
            if (visited[node] == false && (adjMatrix[node * amountOfNodes + src] != 0)) {
                Queue.push(node); // Add to end.
                visited[node] = true;
            }
        }
    }
}

示例输入和输出：

(6, 3) -> Path is: 6

(1, 5) -> Path is: 1 2 3 4

如您所见，它根本无法正确计算路径。我的算法哪里出了问题，我该如何解决？

Answer 1

BFS 涉及以 FIFO 方式访问相邻节点。一旦到达一个节点，就将其所有邻居放入队列，除非它们已经被访问过。

首先，您在迭代相邻节点时出现错字。您想要遍历 top 列，而不是 src 列：

adjMatrix[node * amountOfNodes + top] != 0
//                               ~~^

其次，您当前的path实现存储节点的访问顺序，不是从源到目的地的路径。对于后者，需要存储每个节点的parent，这样就可以通过从child（目的地）到它的parent，grand[=31]来恢复最终的路径=]、great-grandparent、...等

std::vector<int> parent(amountOfNodes, -1);

//...

if (visited[node] == false && (adjMatrix[node * amountOfNodes + top] != 0))
{
    Queue.push(node); // Add to end.
    visited[node] = true;
    parent[node] = top;
}

恢复路径很简单：

int u = dest;            
do
{
    std::cout << u << " ";
    u = parent[u];
}
while (u != -1);

DEMO

广度优先搜索无法找到确实存在的目的地

Breadth First Search fails to find destination that does exist

c++

algorithm

breadth-first-search

adjacency-matrix