广度优先搜索（深搜优化版本）
2024-03-24 18:17:19
发布于：北京
22阅读
0回复
0点赞
汇总
广度优先搜索（Breadth-First Search，BFS）是另一种常见的图遍历算法，与深度优先搜索不同的是，BFS从起始节点开始，依次访问其所有未访问过的邻居节点，然后逐层向外扩展搜索。
BFS算法步骤：
-
将起始节点放入队列：将起始节点放入队列中。
-
标记起始节点为已访问：标记起始节点为已访问。
-
从队列中取出一个节点：从队列中取出一个节点，访问该节点，并且将其所有未访问过的邻居节点放入队列中。
-
重复步骤3：重复步骤3，直到队列为空。
示例代码：
让我们继续使用之前的无向图作为示例来说明BFS算法。同样假设有以下图：
A -- B
| |
C -- D
我们仍然使用邻接表来表示这个无向图，但这次我们会使用队列来实现BFS算法：（C++）
#include <iostream>
#include <vector>
#include <queue>
#include <unordered_set>
using namespace std;
// 定义图的邻接表
unordered_set<char> graph[4] = {{'B', 'C'}, {'A', 'D'}, {'A', 'D'}, {'B', 'C'}};
bool visited[4];
// 广度优先搜索函数
void bfs(char start) {
queue<char> q;
q.push(start);
visited[start - 'A'] = true;
while (!q.empty()) {
char node = q.front();
q.pop();
cout << "Visiting node: " << node << endl;
for (char neighbor : graph[node - 'A']) {
if (!visited[neighbor - 'A']) {
q.push(neighbor);
visited[neighbor - 'A'] = true;
}
}
}
}
int main() {
// 初始化visited数组
for (int i = 0; i < 4; i++) {
visited[i] = false;
}
// 从节点A开始广度优先搜索
bfs('A');
return 0;
}
在这个示例中，我们从节点A开始进行BFS。程序会按照广度优先的顺序访问各个节点，并输出每个节点的名称。通过逐层访问邻居节点，BFS能够探索整个连通图。您可以运行这段代码，并修改图的结构来验证BFS算法的工作原理。
希望这个示例能够帮助您理解广度优先搜索算法的实现及应用。如果您需要更多说明或有任何问题，请随时告诉我！
这里空空如也
有帮助，赞一个