广度优先搜索算法（Breadth First Search，又称宽度优先搜索算法）是最简便的图的搜索算法之一，这一算法也是很多重要的图的算法原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和广度优先搜索类似的思想。广度优先搜索算法属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。

基本思想

广度优先搜索遍历类似于树的按层次遍历。

对于无向连通图，广度优先搜索是从图的某个顶点V0出发，在访问V0之后，依次搜索访问V0的各个未被访问过的邻接点W1，W2，…。然后顺序搜索访问W1的各未被访问过的邻接点，W2的各未被访问过的邻接点，……即从v0开始，由近至远，按层次依次访问与V0有路径相通且路径长度分别为1，2，……的顶点，直至连通图中所有顶点都被访问一次。

广度优先搜索的顺序不是唯一的。具体描述如下：

从图中的某个顶点V出发，访问之；并将其访问标志置为已被访问，即visited[i]=1；
依次访问顶点V的各个未被访问过的邻接点，将V的全部邻接点都访问到；
分别从这些邻接点出发，依次访问它们的未被访问过的邻接点，并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问，直到图中所有已被访问过的顶点的邻接点都被访问到。

依此类推，直到图中所有顶点都被访问完为止。

广度优先搜索在搜索访问一层时，需要记住已被访问的顶点，以便在访问下层顶点时，从已被访问的顶点出发搜索访问其邻接点。所以在广度优先搜索中需要设置一个队列Queue，使已被访问的顶点顺序由队尾进入队列。在搜索访问下层顶点时，先从队首取出一个已被访问的上层顶点，再从该顶点出发搜索访问它的各个邻接点。

算法描述

一般来说，BFS使用队列来实现。在存储数据时，除了需要存储当前状态外，还需要存储当前状态的父状态以及父状态转换过来所执行的操作。

初始状态入队Op :=1；
对队首状态进行操作Op，得到新状态；
检查此状态是否出现过：如果此状态为目标状态，则输出；如果所有操作都已完成，则队首出列，否则Op:=Op+1。
广度优先搜索算法描述

Program Bfs;
  初始化，初始状态存入OPEN表(即队列);
  队列首指针head:=0;尾指针tail:=1;
  repeat
    指针head后移一位，指向待扩展结点;
    for l=1 to max do  {max为产生子结点的规则数}
    begin
     if 子结点符合条件 then
      begin
       tail指针增1，把新结点存入队尾;
       if新结点与原已产生结点重复then删去该结点(取消入队，tail减1)
        else
         if新结点是目标结点then输出并退出;
       end;
     end;
until(head>=tail);{队列空}

算法实例

如图所示，初始化：

在List中选择结点i=1

如果结点i和一条可进入弧关联，则如图所示：

当结点i没有与可进入弧关联之后，则删除结点i，如图所示：

再次选择结点i=2，如图所示

结点i有与可进入弧关联，如图所示：

当结点i没有与可进入弧关联之后，则删除结点i（i=2），如图所示：

把List上的第一个结点变成结点i，则结点i=5

结点i有与可进入弧关联，如图所示：

当结点i没有与可进入弧关联之后，则删除结点i（i=5），如图所示：

把List上的第一个结点变成结点i，则结点i=3；结点i=3没有与可进入弧关联，则删除结点i（i=3），如图所示：

把List上的第一个结点变成结点i，则结点i=4

当结点i没有与可进入弧关联之后，则删除结点i（i=4），如图所示：

把List上的第一个结点变成结点i，则结点i=6

当结点i没有与可进入弧关联之后，删除结点i（i=6）；剩下的结点8、7、9均没有与可进入弧关联，则从List中删除这些结点

广度优先搜索算法的特性

空间复杂度

因为所有节点都必须被储存，因此BFS的空间复杂度为 O(|V| + |E|)，其中 |V|是节点的数目，而|E|是图中边的数目。

另一种说法称BFS的空间复杂度为O(B)，其中B是最大分支系数，而M是树的最长路径长度。由于对空间的大量需求，因此BFS并不适合解非常大的问题。

时间复杂度

最差情形下，BFS必须寻找所有到可能节点的所有路径，因此其时间复杂度为 O(|V| + |E|)，其中 |V|是节点的数目，而 |E| 是图中边的数目。

完全性

广度优先搜索算法具有完全性。这意指无论图形的种类如何，只要目标存在，则BFS一定会找到。然而，若目标不存在，且图为无限大，则BFS将不收敛（不会结束）。

最佳解

若所有边的长度相等，广度优先搜索算法是最佳解——亦即它找到的第一个解，距离根节点的边数目一定最少；但对一般的图来说，BFS并不一定回传最佳解。这是因为当图形为加权图（亦即各边长度不同）时，BFS仍然回传从根节点开始，经过边数目最少的解；而这个解距离根节点的距离不一定最短。这个问题可以使用考虑各边权值，BFS的改良算法成本一致搜寻法（en:uniform-cost search）来解决。然而，若非加权图形，则所有边的长度相等，BFS就能找到最近的最佳解。