BFS(v)//宽度优先搜索G,从顶点ⅴ开始执行 //所有已搜索的顶点i都标记为 Visited(i)=1. // Visited的初始分量值全为0 1. Visited (v=1 2.Q=[;/将Q初始化为只含有一个元素v的队列 3. while Q非空do 4. u=DelHead (Q) for邻接于u的所有顶点wdo if Visited (w)=0 then AdQ(w,Q);//将w放于队列Q之尾 Visited (w)=1 9. endif ndf 11. endwhile 12. end BFS 这里调用了两个函数:AddQ(w,Q)是将w放于队列Q之尾; Delhead(Q)是从队列 Q取第一个顶点,并将其从Q中删除。 定理3.2.1图G的宽度优先搜索算法能够访问G中由v可能到达的所有顶 点。如果记t(v,e)和s(v,e)为算法BFS在任意一个具有v个顶点和E条边的图 G上所花的最大时间和最大空间。则 t(v,E)=6(v+E),s(v,E)=(v)当G由邻接链表表示时 t(v,E)=(v2),s(v,E)=6(v)当G由邻接矩阵表示时 证明略。 由定理2可知,宽度优先搜索算法能够遍历图G的包含ⅴ的连通分支中的所 有顶点。对于不连通的图,可以通过在每个连通分支中选出一个顶点作为起点, 应用宽度搜索算法于每个连通分支,即可遍历该图的所有顶点。 图的宽度优先遍历算法伪代码 BFT(G,v)//图G的宽度优先遍历 for i from 1 to y do Visited(i)=0;/将所有的顶点标记为未被访问 dfo f if Visited (i)==o then BFS (i): endif end bstBFS(v) //宽度优先搜索 G，从顶点 v 开始执行 // 所有已搜索的顶点 i 都标记为 Visited(i)=1. //Visited 的初始分量值全为 0 1. Visited(v)=1; 2. Q=[];//将 Q 初始化为只含有一个元素 v 的队列 3. while Q 非空 do 4. u=DelHead(Q); 5. for 邻接于 u 的所有顶点 w do 6. if Visited(w)=0 then 7. AddQ(w,Q); //将 w 放于队列 Q 之尾 8. Visited(w)=1; 9. endif 10. endfor 11. endwhile 12. end BFS 这里调用了两个函数：AddQ(w,Q)是将 w 放于队列 Q 之尾；DelHead(Q)是从队列 Q 取第一个顶点，并将其从 Q 中删除。 定理 3.2.1 图 G 的宽度优先搜索算法能够访问 G 中由 v 可能到达的所有顶 点。如果记 t(ν ,e)和 s(ν ,e)为算法 BFS 在任意一个具有ν 个顶点和ε 条边的图 G 上所花的最大时间和最大空间。则 t(ν ,ε )=Θ(ν +ε ), s(ν ,ε )=Θ(ν ) 当 G 由邻接链表表示时； t(ν ,ε )=Θ(ν 2 ), s(ν ,ε )=Θ(ν ) 当 G 由邻接矩阵表示时； 证明略。 由定理 2 可知，宽度优先搜索算法能够遍历图 G 的包含 v 的连通分支中的所 有顶点。对于不连通的图，可以通过在每个连通分支中选出一个顶点作为起点， 应用宽度搜索算法于每个连通分支，即可遍历该图的所有顶点。 图的宽度优先遍历算法伪代码 BFT(G, ν ) //图 G 的宽度优先遍历 for i from 1 to ν do Visited(i)=0; //将所有的顶点标记为未被访问 endfor for i from 1 to ν do if Visited(i)==0 then BFS(i); endif endfor end BST