广度优先搜索 - 一霎微雨洒庭轩

2007-08-22

广度优先搜索 - [Algorithms]

版权声明：转载时请以超链接形式标明文章原始出处和作者信息及本声明
 http://conoon.blogbus.com/logs/7858950.html

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

【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.