广度优先搜索无法找到确实存在的目的地
Breadth First Search fails to find destination that does exist
所以我一直在研究 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
如您所见,它根本无法正确计算路径。我的算法哪里出了问题,我该如何解决?
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);
所以我一直在研究 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
如您所见,它根本无法正确计算路径。我的算法哪里出了问题,我该如何解决?
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);