图的广度优先搜索属于图的遍历的一种。
从图中的某一顶点出发，按照某种搜索方法沿着图中的边对图中的所有顶点访问一次且仅访问一次。 注意：树是一种特殊的图，所以树的遍历实际上也可以认为是一种特殊的图的遍历。 在图的遍历过程中，必须记下每个已经访问过的顶点，因此可以设一个辅助数组visited[]来标记顶点是否被访问过。 遍历分为：广度优先搜索和深度优先搜索。
就像一滴水滴到水面的波纹，从中间到两边逐渐的扩散。 处理某个顶点时，一次性发现其所有相邻顶点，未处理顶点加入等待队列。 队列：先入先出就像我们排队，先排队的人，先买到东西。
对于连通图，广度优先搜索会产生一颗广度优先生成树； 基于邻接表存储的广度优先生成树不是唯一的。 邻接矩阵存储表示是唯一的，所以广度优先生成树也是唯一的。
单源最短路径问题
基本思想： 首先访问起始顶点v，接着由v出发，依次访问v的各个未被访问过的邻接顶点w1,w2,…,wi； 然后依次访问w1,w2,…,wi的所有未被访问过的邻接顶点； 再从这些访问过的顶点出发，访问它们所有未被访问过的邻接顶点，直至图中所有顶点都被访问过为止。 若此时图中还有顶点未被访问到，则另选图中一个未被访问过的顶点作为起始点，重复上述过程，直至图中所有顶点都被访问到为止。 Dijkstra单源最短路径算法和Prim最小生成树算法就是用了类似的思想。 BFS遍历图的过程是以v为起始点，由近至远依次访问和v有路径相通且路径长度为1，2，…的顶点。BFS是一种分层的查找过程，每向前走一步可能访问一批顶点，（DFS深度优先搜索有回溯）所以它不是递归的算法。 为了实现逐层的访问，算法必须借助一个辅助队列，以记忆正在访问的顶点的下一层顶点。 伪代码如下：
bool visited[MAX_VERTEX_NUM];//访问标记数组 void BFSTraverse(Graph G){ //对图G进行广度优先遍历 for (i = 0;i < G.vexnum;++i) //G.vexnum为顶点的数量 visited[i] = FALSE;//初始化访问标记数组 InitQueue(Q); //初始化辅助队列Q for (i=0;i < G.vexnum;++i)//从0号顶点开始遍历 if (!vistited[i]) //对每个连通分量调用一次BFS BFS(G,i);//vi未被访问过，从vi开始BFS } void BFS(Graph G,int v){ //从顶点v出发，广度优先遍历图G visit(v); //访问初始顶点v visited[v] = TRUE; //对v做已访问标记 Q.Enqueue(v); //顶点v入队列Q while (!isEmpty(Q)){ u = Q.Dequeue(); //出队列 for (v ∈ G.Adj(u)){ // 遍历u的所有邻接顶点 if (!visited[v]){ //v为u的未被访问的邻接顶点 visit(v); // 访问顶点v visited[v] = TRUE; //对v做已访问标记 Q.Enqueue(v); //顶点v入队列 } } } }例如： 对下图进行广度优先搜索遍历， 我们需要下面的辅助数组： 用个形象的图来说明一下color： 那么，处理该问题的伪代码如下：
BFS(G.s) 输入：图G，源点s 输出：前驱数组pred[],距离数组dist[] 新建一维数组color[1...|V|],pred[1..|V|],dist[1...|V|] 新建空队列Q //初始化 for u ∈ V do color[u] <- WHITE pred[u] <- NULL dist[u] <- ∞ end color[s] <- GRAY dist[s] <- 0 Q.Enqueue(s) //把源点加入 //广度优先搜索 while 等待队列Q非空 do //依次处理所有顶点 u <- Q.Dequeue() //从等待队列取出当前处理顶点u for v ∈ G.Adj[u] do //搜索顶点u的所有相邻顶点 if color[v] == WHITE then //第一次发现顶点v color[v] <- GRAY //标记已发现顶点v为待处理状态 dist[v] <- dist[u] + 1 //记录到源点的距离 pred[v] <- u //记录前驱顶点 Q.Enqueue(v) //加入待处理队列 end end color[u] <- BLACK //标记当前顶点处理完成 end采用邻接表存储方式时，O(V+E)，V、E分别为顶点数、边数 采用邻接矩阵存储方式时，O(V^2)
