广度优先搜索1 2008年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 / \ 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:...
