简介
是一种盲目搜索方法，特点是盲目地展开并检查图中的所有节点。目的是找出两个节点之间的最短距离。
适用问题
求最短距离
特点
- 空间复杂度：由于对空间的大量需求，因此BFS并不适合解非常大的问题，对于类似的问题，应用IDDFS已达节省空间的效果。
- 时间复杂度：最差情形下，BFS必须查找所有到可能节点的所有路径。
- 完全性：广度优先搜索算法具有完全性。这意指无论图形的种类如何，只要目标存在，则BFS一定会找到。然而，若目标不存在，且图为无限大，则BFS将不收敛（不会结束）。
- 最佳解：若所有边的长度相等，广度优先搜索算法是最佳解——亦即它找到的第一个解，距离根节点的边数目一定最少；但对一般的图来说，BFS并不一定回传最佳解。这是因为当图形为加权图（亦即各边长度不同）时，BFS仍然回传从根节点开始，经过边数目最少的解；而这个解距离根节点的距离不一定最短。这个问题可以使用考虑各边权值，BFS的改良算法成本一致搜索法来解决。然而，若非加权图形，则所有边的长度相等，BFS就能找到最近的最佳解。
算法流程
（1）选中第一个被访问的顶点；
（2）对顶点作已访问过的标志；
（3）依次访问已访问顶点的第1,2，……个未被访问过的邻接顶点，并进行标记；转向（3）；
（4）如果还有顶点未被访问，则选中一个起始顶点，转向（2）；
（5）所有顶点都被访问到，则结束。
广度优先搜索一般是用队列实现的。同前面一样，也需要方法来表示某个顶点有没有被访问过。广度优先搜索的伪代码如下：·
void BFS(图)
{
for（所有顶点）
{
若该顶点未被访问
{
bfs（该顶点）;
}
}
}
bfs（某个顶点）指的是从某个顶点开始进行广度优先搜索遍历。
bfs(某个顶点)
{
初始化一个队列queue并将这个顶点放入队列；
while（queue不为空）
{
访问队头顶点s；//可以cout打印，也可以储存在一个vector中
标记s为已遍历；
出队pop_front()；
遍历p的所有邻接顶点
{
若该顶点没被访问过，入队；
}
}
}