一、基本思想
BFS的基本思想是使用队列(Queue)数据结构来实现。队列是一种先进先出(FIFO)的数据结构,这符合BFS逐层访问节点的需求。在BFS中,首先将起始节点加入队列,并标记为已访问。然后,从队列中取出一个节点,访问其所有未被访问的相邻节点,并将这些相邻节点加入队列。重复这个过程,直到队列为空,即所有可达的节点都被访问过。
二、算法步骤
1、初始化:创建一个队列,并将起始节点加入队列,同时标记为已访问。
2、循环访问:当队列不为空时,执行以下步骤:
(1)从队列中取出一个节点(队首节点)。
(2)访问该节点(例如,打印节点值、处理节点数据等)。
(3)遍历该节点的所有未被访问的相邻节点。
(4)对于每个相邻节点,如果它未被访问过,则将其加入队列,并标记为已访问。
3、结束条件:当队列为空时,算法结束。此时,所有可达的节点都已被访问过。
三、应用场景
BFS广泛应用于图论中的各种问题,包括但不限于:
1、最短路径问题:在无权图中,BFS可以找到从一个节点到另一个节点的最短路径(以边的数量计)。
2、连通性问题:判断图中的所有节点是否都连通,或者某个节点是否可以到达图中的其他节点。
3、拓扑排序:对有向无环图(DAG)进行排序,使得对于任意一条有向边u->v,节点u都在节点v之前。
4、层次遍历:在树形结构中,BFS可以用于层次遍历,即按层级访问树的节点。
四、优点与缺点
1、优点:
BFS能够找到从起始节点到目标节点的最短路径(在无权图中)。
适用于解决连通性、拓扑排序等问题。
2、缺点:
当图非常大或非常稀疏时,BFS可能需要访问大量的节点才能找到目标节点或确定无路径可达。
在某些情况下,如寻找所有路径或评估路径的多样性时,BFS可能不如深度优先搜索(DFS)有效。
五、代码示例
以下是一个简单的BFS代码示例,用于在无权图中进行搜索:
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
// 假设图使用邻接表表示
vector<vector<int>> graph;
vector<bool> visited;
void bfs(int start) {
queue<int> q;
visited.assign(graph.size(), false); // 初始化访问标记
visited[start] = true; // 标记起始节点为已访问
q.push(start); // 将起始节点加入队列
while (!q.empty()) {
int node = q.front(); // 取出队首节点
q.pop(); // 弹出队首节点
cout << node << " "; // 访问节点(这里只是打印节点值)
// 遍历当前节点的所有相邻节点
for (int neighbor : graph[node]) {
if (!visited[neighbor]) { // 如果相邻节点未被访问过
visited[neighbor] = true; // 标记为已访问
q.push(neighbor); // 加入队列以便后续访问
}
}
}
}
int main() {
// 示例:构建一个图并调用BFS
// ...(图的构建代码省略)
bfs(0); // 假设从节点0开始搜索
return 0;
}
标签:优先,标记,队列,BFS,访问,visited,广度,数据结构,节点
From: https://blog.csdn.net/qq_39311377/article/details/141369366