文档介绍：广度优先搜索12008年07月26日星期六下午03:26§2广度优先搜索BFS   在深度优先搜索算法中,是深度越大的结点越先得到扩展。如果在搜索中把算法改为按结点的层次进行搜索,本层的结点没有搜索处理完时,不能对下层结点进行处理,即深度越小的结点越先得到扩展,也就是说先产生的结点先得以扩展处理,这种搜索算法称为广度优先搜索法。英语中用Breadth-First-Search表示,所以我们也把广度优先搜索法简称为BFS。1、广度优先搜索的基本思想   从图中某一顶点Vo出发,首先访问Vo相邻的所有未被访问过的顶点V1、V2、……Vt;再依次访问与V1、V2、……Vt相邻的且未被访问过的所有顶点。如此继续,直到访问完图中所有的顶点。   如果用广度优先法对下图中结点进行搜索,从结点V1出发,先搜索处理它的子结点V2和V3,即深度为2的结点;然后搜索深度为3的子结点V4、V5、V6、V7;最后搜索深度为4的结点V8和V9。整个搜索的次序与结点产生的次序完全一致。深度__V1__1/\V2V32/\/\V4V5V6V73/\:   1)从某个顶点出发开始访问,被访问的顶点作相应的标记,并输出访问顶点号;   2)从被访问的顶点出发,依次搜索与该顶点有边的关联的所有未被访问的邻接点,并作相应的标记。   3)再依次根据2)中所有被访问的邻接点,访问与这些邻接点相关的所有未被访问的邻接点,直到所有顶点被访问为止。   【算法过程】procedureguangdu(i);beginwrite(i);v[i]:=true;insert(q,i);{q是队列,i进队}repeatk:=delete(q);{出队}forj:=1tondoif(a[k,j]=1)and(notv[j])thenbeginwrite(j);v[j]:=true;insert(q,j);end;until队列q为空;   【实际应用】:实际应用的算法流程图通常如下:   【问题描述】如下图,找出C1到C6的一条最短路径并求出其路程总长度(采用广度优先搜索的顶点访问序列为C1,C2,C3,C4,C5,C6)。   【Pascal程序】programtu3bfs;typefg=setof1..6;constlink:array[1..5,1..6]ofinteger=((0,4,8,0,0,0),(4,0,3,4,6,0),(8,3,0,2,2,0),(0,4,2,0,4,9),(0,6,2,4,0,4));varpnt,city:array[1..10]of0..6;flag:fg;r,k,head,tail:integer;procedureprint;varn,i,cost,y:integer;  s:array[1..7]of1..6;begin  y:=tail;n:=0;  cost:=0;  whiley>0dobegininc(n);s[n]:=y;y:=pnt[y]end;  writeln('minpath=',n-1);  write('1');  fori:=n-1downto1do   begin   write('->',s[i]);   cost:=cost+link[s[i+1],s[i]];   end;  writeln;  writeln('cost=',cost);  end;beginflag:=[1];pnt[1]:=0;city[1]:=1;head:=0;tail:=1;repeathead:=head+1;k:=city[head];forr:=2to6do  ifnot(rinflag)and(link[k,r]>0)then  begin  inc(tail);city[tail]:=r;  pnt[tail]:=head;  flag:=flag+[r];  ifr=6thenbeginprint;haltend;  end;untilhead>=tail;readln;end.§2-2广度优先搜索实例【例题】八数码难题(Eight-puzzle)。在3X3的棋盘上,摆有8个棋子,在每个棋子上标有1~8中的某一数字。棋盘中留有一个空格。空格周围的棋子可以移到空格中。要求解的问题是,给出一种初始布局(初始状态)和目标布局(目标状态),找到一种最少步骤的移动方法,实现从初始布局到目标布局的转变。初始状态和目标状态如下:初始状态目标状态2831231648475765求解本题我们可以分3步进行。   问题分析:   由于题目要找的解是达到目标的最少步骤,因此可以这样来设计解题的方法:   初始状态为搜索的出发点,把移动一步后的布局全部找到,检查是否有达到目标的布局,如果没有,再从这些移动