简介
是一种盲目搜索方法,特点是盲目地展开并检查图中的所有节点。目的是找出两个节点之间的最短距离。
适用问题
求最短距离
特点
- 空间复杂度:由于对空间的大量需求,因此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的所有邻接顶点
{
若该顶点没被访问过,入队;
}
}
}