第1个回答 2011-02-27
一、广度优先搜索
在深度优先搜索算法中，是深度越大的结点越先得到扩展。如果在搜索中把算法改为按结点的层次进行搜索，本层的结点没有搜索处理完时，不能对下层结点进行处理，即深度越小的结点越先得到扩展，也就是说先产生的结点先得以扩展处理，这种搜索算法称为广度优先搜索法。英语中用Breadth-First-Search表示，所以我们也把广度优先搜索法简称为BFS。
广度优先搜索算法（又称宽度优先搜索）是最简便的图的搜索算法之一，这一算法也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。
二、广度优先搜索基本算法：
1）从某个顶点出发开始访问，被访问的顶点作相应的标记，并输出访问顶点号；
2）从被访问的顶点出发，依次搜索与该顶点有边的关联的所有未被访问的邻接点，并作相应的标记。
3）再依次根据2）中所有被访问的邻接点，访问与这些邻接点相关的所有未被访问的邻接点，直到所有顶点被访问为止。
三、广度优先搜索算法描述：
Program Bfs；
初始化，初始状态存入队列表；
队列首指针head:=0;尾指针tail:=1；
repeat
指针head:=head+1，指向待扩展结点；
for I=1 to max do {max为产生子结点的规则数}
begin
if 子结点符合条件 then
begin
tail指针增1，把新结点存入列尾；
if新结点与原已产生结点重复then删去该结点（取消入队，tail减1）
else
if新结点是目标结点then输出并退出；
end;
end;
until(tail>=head); {队列空}
四、广度优先搜索注意事项
1、每生成一个子结点，就要提供指向它们父亲结点的指针。当解出现时候，通过逆向跟踪，找到从根结点到目标结点的一条路径。
2、生成的结点要与前面所有已经产生结点比较，以免出现重复结点，浪费时间，还有可能陷入死循环。
3、如果目标结点的深度与“费用”（如：路径长度）成正比，那么，找到的第一个解即为最优解，这时，搜索速度比深度搜索要快些；如果结点的“费用”不与深度成正比时，第一次找到的解不一定是最优解。
4、广度优先搜索的效率还有赖于目标结点所在位置情况，如果目标结点深度处于较深层时，需搜索的结点数基本上以指数增长。