AI摘要 此内容由AI根据正文内容自动生成

BFS（广度优先搜索）就像往池塘丢石头，水波一圈圈向外扩散，按距离从近到远访问所有节点。它用队列实现，先访问距离1的点，再距离2的点，直到遍历完整个图。

标签：BFS广度优先搜索图论队列寻路算法

1. BFS是什么

BFS（Breadth-First Search）全称广度优先搜索，也叫宽度优先搜索，是一个非常经典、也非常容易考到的寻路算法。你可以想象往平静的池塘扔一块石头，水波会一圈一圈向外扩展，BFS搜索的逻辑就类似于水波：从起点出发出发，优先遍历与起点距离为1的点，遍历完成后，再遍历与起点距离为2的所有点，以此向外扩散。

2. 具体怎么实现

假设我们有一张有向图：

v1 -----> v2
|      ↗
|    v3
V ↗    ↘
v4       v5

要求从点v1开始，用BFS序遍历所有点。

1. 遍历与v1距离为0的点，得到的结果有{v1}；

2. 遍历与v1距离为1的点，得到的结果有{v2,v4}；

3. 遍历与v1距离为2的点，得到的结果有{v3}；

4. 遍历与v1距离为3的点，得到的结果有{v5}；

5. 遍历与v1距离为4的点，得到的结果为∅，遍历结束。

将所有结果拼接在一起，就得到了最终的BFS序：{v1,v2,v4,v3,v5}。

在上面的过程中，不难发现，要找与源点距离为x的点，只需要看所有与源点距离为x-1的点，然后枚举它们所指向的所有点即可，特别地，如果点已经被访问过，就不需要再次访问了。

3. 代码怎么写

我们可以开一个队列，来记录目前遍历过的点，由队列里存储的点，即可扩展出新的一层，具体代码如下：

void bfs(int n,int st,bool g[MAXN][MAXN]){
	// n：节点数
	// st：起始节点
	// g：邻接矩阵
	std::queue<int> q;// #include<queue>，如果你用万能头当我没说
	q.push(st);
	while(!q.empty()){
		int u=q.front();
		q.pop();
		std::cout<<u<<'\n';// #include<iostream>，如果你用万能头当我没说
		for(int i=1;i<=n;i++)
			if(g[u][i])
				q.push(i);
	}
}