广度优先搜索(BFS)

简介

是一种盲目搜索方法，特点是盲目地展开并检查图中的所有节点。目的是找出两个节点之间的最短距离。

适用问题

求最短距离

特点

• 空间复杂度：由于对空间的大量需求，因此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的所有邻接顶点
                {
                    若该顶点没被访问过，入队；
                }
         }
}

广度优先搜索(BFS)

原文：https://www.cnblogs.com/wichellc/p/14946452.html