|
在深度优先搜索算法中，是深度越大的结点越先得到扩展。如果在搜索中把算法改为按结点的层次进行搜索， 本层的结点没有搜索处理完时，不能对下层结点进行处理，即深度越小的结点越先得到扩展，也就是说先产生 的结点先得以扩展处理，这种搜索算法称为广度优先搜索法。英语中用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 42.广度优先搜索基本算法：
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.
|
网友评论：（只显示最新10条。评论内容只代表网友观点，与本站立场无关！） 
