常用算法——广度优先搜索

常用算法——广度优先搜索

佚名

在深度优先搜索算法中，是深度越大的结点越先得到扩展。如果在搜索中把算法改为按结点的层次进行搜索，本层的结点没有搜索处理完时，不能对下层结点进行处理，即深度越小的结点越先得到扩展，也就是说先产生的结点先得以扩展处理，这种搜索算法称为广度优先搜索法。英语中用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
      /      \
    V2        V3           2
   /  \      /  \
 V4    V5  V6    V7        3
          /  \
         V8  V9            4

2.广度优先搜索基本算法：
    1）从某个顶点出发开始访问，被访问的顶点作相应的标记，并输出访问顶点号；
    2）从被访问的顶点出发，依次搜索与该顶点有边的关联的所有未被访问的邻接点，并作相应的标记。
    3）再依次根据2）中所有被访问的邻接点，访问与这些邻接点相关的所有未被访问的邻接点，直到所有顶点被访问为止。
    【算法过程】

procedure guangdu(i);
 begin
   write(i);
   v[i]:=true;
   insert(q,i);{q是队列，i进队}
   repeat
     k:=delete(q)；{出队}
     for j:=1 to n do
     if (a[k,j]=1) and (not v[j]) then
     begin
     write(j);
     v[j]:=true;
     insert(q,j);
     end;
   until 队列q为空;

【实际应用】：实际应用的算法流程图通常如下：

【问题描述】如下图，找出C1到C6的一条最短路径并求出其路程总长度(采用广度优先搜索的顶点访问序列为C1,C2,C3,C4,C5,C6)。

    【Pascal程序】
program tu3bfs;
type fg=set of 1..6;
const link:array[1..5,1..6] of integer=((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));
var pnt,city:array[1..10] of 0..6;
flag:fg;
r,k,head,tail:integer;
procedure print;
var n, i,cost,y:integer;
   s:array[1..7] of 1..6;
begin
   y:=tail;n:=0;   cost:=0;
   while y>0 do begin inc(n);s[n]:=y;y:=pnt[y] end;
   writeln('minpath=',n-1);
   write('1');
   for i:=n-1 downto 1 do
    begin
    write('->',s[i]);
    cost:=cost+link[s[i+1],s[i]];
    end;
   writeln;
   writeln('cost=',cost);
   end;
begin
flag:=[1];
pnt[1]:=0; city[1]:=1;
head:=0;tail:=1;
repeat
head:=head+1;
k:=city[head];
for r:=2 to 6 do
   if not(r in flag) and (link[k,r]>0) then
   begin
   inc(tail);city[tail]:=r;
   pnt[tail]:=head;
   flag:=flag+[r];
   if r=6 then begin print;halt end;
   end;
until head>=tail;
readln;
end.