广度优先搜索

（一）深度优先搜索遍历算法

深度优先搜索的过程

深度优先搜索所遵循的搜索策略是尽可能“深”地搜索图。在深度优先搜索中，对于最新发现的节点，如果它还有以此为起点而未搜索的边，就沿此边继续搜索下去。当节点v的所有边都己被探寻过，搜索将回溯到发现节点v有那条边的始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被发现为止。即

⒈以给定的某个顶点V0为起始点，访问该顶点；

⒉选取一个与顶点V0相邻接且未被访问过的顶点V1，用V1作为新的起始点，重复上述过程；

⒊当到达一个其所有邻接的顶点都已被访问过的顶点Vi时，就退回到新近被访问过的顶点Vi- 1，继续访问Vi-1尚未访问的邻接点，重复上述搜索过程； ⒋直到从任意一个已访问过的顶点出发，再也找不到未被访问过的顶点为止，遍历便告完成。

这种搜索的次序体现了向纵深发展的趋势，所以称之为深度优先搜索。

深度优先搜索算法描述：

程序实现有两种方式--递归与非递归。 一、递归

递归过程为：

Procedure DEF-GO(step) for i:=1 to max do

if 子结点符合条件 then 产生新的子结点入栈；

if 子结点是目标结点 then 输出 else DEF-GO(step+1)； 栈顶结点出栈； endif； enddo； 主程序为： Program DFS； 初始状态入栈； DEF-GO(1)；

二、非递归

Program DEF(step)； step:=0； repeat

step:=step+1； j:=0；p:=false repeat j:=j+1；

if 结点符合条件 then

产生子结点入栈；

if 子结点是目标结点 then 输出 else p:=true； else

if j>=max then 回溯 p:=false； endif；

until p=true； until step=0； 回溯过程如下： Procedure BACK； step:=step-1；

if step>0 then 栈顶结点出栈 else p:=true；

例如 八数码难题--已知８个数的起始状态如图1（ａ），要得到目标状态为图1(ｂ）。 ２ ８ ３ １ ２ ３ １ ６ ４ ８ ■ ４ ７ ■ ５ ７ ６ ５ （ａ） （ｂ） 图 1

求解时,首先要生成一棵结点的搜索树，按照深度优先搜索算法，我们可以生成图1的搜索树。图中，所有结点都用相应的数据库来标记，并按照结点扩展的顺序加以编号。其中，我们设置深度界限为５。粗线条路径表示求得的一个解。从图中可见，深度优先搜索过程是沿着一条路径进行下去，直到深度界限为止，回溯一步，再继续往下搜索，直到找到目标状态或OPEN表为空为止。

图1 程序：

program No8_DFS; {八数码的深度优先搜索算法}

Const

Dir : array[1..4,1..2]of integer = ((1,0),(-1,0),(0,1),(0,-1));

maxN = 15; ｛可以承受的最大深度｝ Type

T8No = array[1..3,1..3]of integer; tList = record state : T8No; x0,y0 : integer; end; Var

Source,Target : T8No;

List,Save : array[0..maxN]of tList; ｛综合数据库，最优解路径｝ Open,Best : integer;

procedure GetInfo; {见程序1} Function Same(A,B : T8No):Boolean; {见程序1} function Not_Appear(New : tList):boolean; {见程序1}

procedure Move(N : tList;d : integer;var ok : boolean;var New : tList);

{见程序1}

procedure GetOutInfo; {输出｝ var i,x,y : integer; begin

writeln('total = ',best); for i:=1 to best+1 do begin for x:=1 to 3 do begin

for y:=1 to 3 do write(Save[i].State[x,y],' '); writeln; end; writeln; end; end;

Procedure Recursive; ｛递归搜索过程｝ Var i : integer; New: tList; ok : boolean; Begin

If Open-1>=Best then exit;

If Same(List[Open].state,Target) then begin ｛如果找到解，保存当前最优解｝ Best:=Open-1; Save:=List; end;

For i:=1 to 4 do begin ｛依次选用规则｝ Move(List[Open],i,OK,New);

if ok and not_Appear(New) then begin ｛如果没有重复｝ inc(open); ｛插入综合数据库｝ List[Open]:=New;

Recursive; {继续搜索} dec(Open); {退栈} End; End; End;

procedure Main; {搜索主过程} var x,y : integer; begin

List[1].state:=Source; {初始化} for x:=1 to 3 do

for y:=1 to 3 do if Source[x,y]=0 then begin List[1].x0:=x; List[1].y0:=y; end;

Best:=MaxN;

Open:=1;

Recursive; {开始搜索} If Best=maxint then writeln('No answer') Else GetOutInfo; end;

Begin

Assign(Input,'input.txt');ReSet(Input);

Assign(Output,'Output.txt');ReWrite(Output); GetInfo; Main;

Close(Input);Close(Output); End.

上面的八数码程序利用到了递归来实现，其实深度优先搜索还有一种无需递归的实现方式，下面我们介绍一下深度优先的一般实现方法：递归算法和非递归算法。

递归算法伪代码：

procedure DFS_ recursive(N);

1. if N=target then 更新当前最优值并保存路径; 2. for r:=1 to 规则数 do [ 3. New:=Expand(N,r)

4. if 值节点New符合条件 then [ 5. 产生的子节点New压入栈; 6. DFS_recursive(i+1); 7. 栈顶元素出栈; 8. ] 9. ]

program DFS; 1. 初始化;

2. DFS_recursive(N);

非递归算法伪代码： procedure Backtracking; 1. dep:=dep-1;

2. if dep>0 then 取出栈顶元素 3. else p:=true;

program DFS; 1. dep:=0; 2. Repeat

3. dep:=dep+1; 4. j:=0;brk:=false; 5. Repeat

6. j:=j+1;

7. New=Expand(Track[dep],j); 8. if New 符合条件 then [

9. 产生子节点New并将其压栈;

10. If 子节点New=target then 更新最优值并出栈 11. else brk:=true; 12. ]

13. else if j>=规则数 then Backtracking 14. else brk:=false; 15. Until brk=true 16. Until dep=0;

两种方式本质上是等价，但两者也时有区别的。 1． 递归方式实现简单，非递归方式较之比较复杂；

递归方式需要利用栈空间，如果搜索量过大的话，可能造成栈溢出，所以在栈空间无法满足的情况下，选用非递归实现方式较好。

（二）广度优先搜索遍历算法

一．宽度优先搜索的过程

宽度优先搜索算法（又称宽度优先搜索）是最简便的图的搜索算法之一，这一算法也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。

宽度优先算法的核心思想是：从初始节点开始，应用算符生成第一层节点，检查目标节点是否在这些后继节点中，若没有，再用产生式规则将所有第一层的节点逐一扩展，得到第二层节点，并逐一检查第二层节点中是否包含目标节点。若没有，再用算符逐一扩展第二层的所有节点 ，如此依次扩展，检查下去，直到发现目标节点为止。即

⒈从图中的某一顶点V0开始，先访问V0；

⒉访问所有与V0相邻接的顶点V1，V2，......，Vt；

⒊依次访问与V1，V2，......，Vt相邻接的所有未曾访问过的顶点； ⒋循此以往，直至所有的顶点都被访问过为止。

这种搜索的次序体现沿层次向横向扩长的趋势，所以称之为广度优先搜索。

二、广度优先搜索算法描述：

Program Bfs；

初始化，初始状态存入OPEN表；

队列首指针head:=0;尾指针tail:=1； repeat

指针head后移一位，指向待扩展结点；

for I=1 to max do {max为产生子结点的规则数} begin

if 子结点符合条件 then begin

tail指针增1，把新结点存入列尾；

if新结点与原已产生结点重复then删去该结点（取消入队，tail减1）

else

if新结点是目标结点then输出并退出； end; end;

until(tail>=head); {队列空}

三、广度优先搜索注意事项：

1、每生成一个子结点，就要提供指向它们父亲结点的指针。当解出现时候，通过逆向跟踪，找到从根结点到目标结点的一条路径。

2、生成的结点要与前面所有已经产生结点比较，以免出现重复结点，浪费时间，还有可能陷入死循环。

3、如果目标结点的深度与“费用”（如：路径长度）成正比，那么，找到的第一个解即为最优解，这时，搜索速度比深度搜索要快些；如果结点的“费用”不与深度成正比时，第一次找到的解不一定是最优解。

4、广度优先搜索的效率还有赖于目标结点所在位置情况，如果目标结点深度处于较深层时，需搜索的结点数基本上以指数增长。

下面我们看看怎样用宽度优先搜索来解决八数码问题。

例如 图2给出广度优先搜索应用于八数码难题时所生成的搜索树。搜索树上的所有结点都标记它们所对应的状态，每个结点旁边的数字表示结点扩展的顺序。粗线条路径表明求得的一个解。从图中可以看出，扩展２６个结点和生成４６个结点之后，才求得这个解。此外，直接观察此图表明，不存在有更短走步序列的解。

图2 广度优先搜索图

程序实现算法：

Program BFS；

建立数据库data；数据库赋初值；

设队列头指针H:=0；队列尾指针L:=1； repeat

取下一个H所指的结点；

for i:=1 to max do {i为产生新结点规则编号} begin

L增1，把新结点存入数据库队尾；记录父结点的位置； if 新结点与原有结点重复 then 删去该结点(L减1) else

if 新结点为目标结点 then 输出并退出； end； end；

until H>=L {队列为空}

程序：

program 8no_bfs; {八数码的宽度优先搜索算法}

Const

Dir : array[1..4,1..2]of integer {四种移动方向，对应产生式规则} = ((1,0),(-1,0),(0,1),(0,-1)); N=10000; Type

T8No = array[1..3,1..3]of integer;

TList = record

Father : integer; {父指针} dep : byte; {深度} X0,Y0 : byte; {0的位置} State : T8No; {棋盘状态 } end; Var

Source,Target : T8No;

List : array[0..10000] of TList; {综合数据库 }

Closed,Open,Best : integer { Best表示最优移动次数} Answer : integer; {记录解} Found : Boolean; {解标志}

procedure GetInfo; {读入初始和目标节点} var i,j : integer;

begin

for i:=1 to 3 do

for j:=1 to 3 do read(Source[i,j]); for i:=1 to 3 do

for j:=1 to 3 do read(Target[i,j]); end;

procedure Initialize; {初始化} var x,y : integer; begin

Found:=false;

Closed:=0;Open:=1;

with List[1] do begin

State:=Source;dep:=0;Father:=0; For x:=1 to 3 do For y:=1 to 3 do

if State[x,y]=0 then Begin x0:=x;y0:=y; End; end; end;

Function Same(A,B : T8No):Boolean; {判断A,B状态是否相等 } Var i,j : integer; Begin

Same:=false;

For i:=1 to 3 do for j:=1 to 3 do if A[i,j]<>B[i,j] then exit; Same:=true; End;

function Not_Appear(New : tList):boolean; {判断New是否在List中出现 } var i : integer; begin

Not_Appear:=false;

for i:=1 to Open do if Same(New.State,List[i].State) then exit; Not_Appear:=true; end;

procedure Move(N : tList;d : integer;var ok : boolean;var New : tList); {将第d条规则作用于N得到New,OK是New是否可行的标志 } var x,y : integer; begin

X := N.x0 + Dir[d,1]; Y := N.y0 + Dir[d,2]; {判断New的可行性}

If not ((X > 0) and ( X < 4 ) and ( Y > 0 ) and ( Y < 4 )) then begin ok:=false;exit end;

New.State:=N.State; {New=Expand(N,d)} New.State[X,Y]:=0;

New.State[N.x0,N.y0]:=N.State[X,Y]; New.X0:=X;New.Y0:=Y; end;

procedure Add(new : tList); {插入节点New} begin

If not_Appear(New) then Begin Inc(Open); List[Open] := New; end; end;

procedure Expand(Index : integer; var N : tList); var i : integer; New : tList; OK : boolean; Begin

If Same(N.State , Target) then begin Found := true; Best :=N.Dep; Answer:=Index; Exit; end;

For i := 1 to 4 do begin Move(N,i,OK,New); if not ok then continue;

New.Father := Index; New.Dep :=N.dep + 1; Add(New); end; end;

procedure GetOutInfo; procedure Outlook(Index : integer); var i,j : integer; begin

if Index=0 then exit;

Outlook(List[Index].Father);

with List[Index] do for i:=1 to 3 do begin

for j:=1 to 3 do write(State[i,j],' ');

{如果New没有在List出现 } {New加入Open表 } {扩展N的子节点} {如果找到解} {依次使用４条规则} {输出}

{递归输出每一个解}

end; writeln; end; begin

Writeln('Total = ',Best); Outlook(Answer); end;

procedure Main; {搜索主过程} begin Repeat

Inc(Closed);

Expand(Closed,List[Closed]); {扩展Closed} Until (Closed>=Open) or Found;

If Found then GetOutInfo {存在解} else Writeln('No answer'); {无解} end;

Begin

Assign(Input,'input.txt');ReSet(Input);

Assign(Output,'Output.txt');ReWrite(Output); GetInfo; Initialize; Main;

Close(Input);Close(Output); End.

例1 在一个瓶中装有80毫升化学溶剂，实验中需要精确地平分成两份，没有量具，只有两个杯子，其中一个杯子的容量是50毫升，另一个是30毫升，试设计一个程序将化学溶剂对分成两个40毫升，并以最少步骤给出答案。

分析:三个杯子水的初始状态为:８０、０、０，生成新结点状态的方法为：将一个不空的杯子水倒入一个不满的杯中，且结点状态不重复，直到生成目标结点为止。

算法步骤:

⒈数据库: 用数组d构成存放生成结点(杯子水状态)的队；数组p作为指向父结点的指针；t和s作为队头与队尾指针。 ⒉结点的产生:

(1)将结点中不空的杯子水倒入一个不满的杯子中，生成新的结点并记下父结点位置； (2)判断新结点是否已生成过， 以避免死循环； (3)生成的结点若为目标结点，输出。 ⒊搜索策略: 广度优先搜索。

源程序如下:

program ex3; type

status= array [1..3] of integer; const

v: array [1..3] of integer =(80，50,30); var

d: array [1..200] of status; p: array [1..200] of integer; t,s,i,j: integer;

procedure draw(f: integer);{输出} var

m: array [1..20] of integer; i,j,k: integer; begin j:=0;

while f<>1 do begin inc(j); m[j]:=f; f:=p[f]; end; writeln;

writeln('Start: ',d[1,1]:3,d[1,2]:3,d[1,3]:3); for i:=j downto 1 do begin

write('Step No.',j+1-i,': ');

for k:=1 to 3 do write(d[m[i],k]:3); writeln; end;

writeln('End.'); halt; end;

function exampass(w: integer): boolean;{新结点是否以前生成过} var

i: integer; begin

for i:=1 to w-1 do

if (d[i,1]=d[w,1]) and (d[i,2]=d[w,2]) and (d[i,3]=d[w,3]) then begin

exampass:=false; exit; end;

exampass:=true; end;

function isobject(w: integer): boolean;{是否为目标结点} begin

if (d[w,1]=40) and (d[w,2]=40) then isobject:=true else isobject:=false; end;

begin {生成新结点,将一个不空的杯子水倒入一个不满的杯子中} d[1,1]:=80; d[1,2]:=0; d[1,3]:=0; p[1]:=0; t:=1; s:=2; repeat

for i:=1 to 3 do if d[t,i]<>0 then for j:=1 to 3 do

if (i<>j) and (d[t,j]<>v[j]) then begin d[s]:=d[t];

d[s,j]:=d[s,j]+d[s,i]; d[s,i]:=0;

if d[s,j]>v[j] then begin d[s,i]:=d[s,j]-v[j]; d[s,j]:=v[j]; end; p[s]:=t;

if exampass(s) then begin

if isobject(s) then draw(s); inc(s); end; end; inc(t); until t>=s;

writeln('NoWay'); end.

例2 跳棋的原始状态如下图。其中"0"表示空格，"-"表示白子，"+"表示黑子，"1--7"表示棋盘格编号。跳棋的规则是：

⒈任意一个棋子可移到相邻的空位上；

⒉可跳过一个或两个棋子到空位上，与跳过的棋子的颜色无关； ⒊棋子向左向右跳不限。

例如：4到1、5到4、3到5、6到3是成功的四步走法。请编一程序，用10步完成从原始状态跳变成目标状态。要求打印跳每一步后的状态。用数字表示棋盘格子的代号。 1 2 3 4 5 6 7 原始位置 0 - - - + + + 目标位置 + + + - - - 0

分析:此题可以用广度与深度搜索两种方法求解，通过运行两种解法的程序，我们可以粗略地知道两种算法的区别。

算法步骤:

⒈数据库：数组ｇ构成队，存放棋子的状态；数组ｐ作为指针指向其父结点位置；ｔ与ｓ分别表示队头与队尾指针。

⒉结点的产生：与位置间距-3到3的棋子可移入空位，生成新结点状态。 ⒊搜索策略：广度优先搜索。

源程序如下:

program ex143-1; {广度优先搜索} uses time; type

status=string[7]; const

start: status ='0---+++'; obj: status ='+++---0'; var

a,b,c: timetype;

g: array [1..200] of status; p: array [1..200] of integer; i,j,k: integer; t,s: integer;

procedure draw(f: integer);{输出} var

m: array [1..10] of integer; i,j: integer; begin j:=0;

while f<>1 do begin inc(j); m[j]:=f; f:=p[f]; end; writeln;

writeln('Start: ',start); for i:=j downto 1 do

writeln('Step No.',j+1-i,': ',g[m[i]]); writeln('End'); gettimenow(b); howlong(a,b,c);

printtime('Time Take: ',c); halt; end;

function exampass(w: integer): boolean;{判断结点有否重复} var

i: integer; begin

for i:=1 to w-1 do

if g[i]=g[w] then begin exampass:=false; exit; end;

exampass:=true; end;

begin {生成新结点} gettimenow(a);

g[1]:=start; p[1]:=0; t:=1; s:=2; repeat

k:=pos('0',g[t]); for i:=-3 to 3 do

if (i<>0) and (k+i>=1) and (k+i<=7) then begin g[s]:=g[t];

g[s,k]:=g[s,k+i]; g[s,k+i]:='0'; p[s]:=t;

if exampass(s) then begin if g[s]=obj then draw(s); inc(s); end; end; inc(t); until t>=s;

writeln('NoWay'); end.

算法骤(二):

⒈数据库：数组ｇ构成堆栈，存放棋子的状态。

⒉结点的产生：与空位置间距－３到３的棋子可移入空位，生成新结点状态。 ⒊搜索策略：含有深度界限的深度优先搜索。

源程序如下:

program ex143-2; {深度优先搜索} uses time; type

status=string[7]; const

start: status ='0---+++'; obj: status ='+++---0'; var

a,b,c: timetype;

g: array [0..10] of status;

i,j,k: integer; procedure draw;{输出} var

i,j: integer; begin

writeln('Start: ',start); for i:=1 to 10 do

writeln('Step No.',i,': ',g[i]); writeln('End'); gettimenow(b); howlong(a,b,c);

printtime('Take Time: ',c); halt; end;

function exampass(w: integer): boolean;{判断有否重复状态} var

i: integer; begin

for i:=1 to w-1 do

if g[i]=g[w] then begin exampass:=false; exit; end;

exampass:=true; end;

procedure run(t: integer);{搜索生成新结点} var

i,k: integer; begin

k:=pos('0',g[t-1]); for i:=-3 to 3 do

if (i<>0) and (k+i>=1) and (k+i<=7) then begin g[t]:=g[t-1];

g[t,k]:=g[t,k+i]; g[t,k+i]:='0'; if exampass(t) then if g[t]=obj then draw else

if t<10 then run(t+1); end; end; begin

gettimenow(a); g[0]:=start; run(1);

end.

运行两种算法程序可以发现，广度优先搜索运行速度比深度优先搜索快。 那么深度优先搜索与广度优先搜索算法有何区别呢？

通常深度优先搜索法不全部保留结点，扩展完的结点从数据库中弹出删去，这样，一般在数据库中存储的结点数就是深度值，因此它占用空间较少。所以，当搜索树的结点较多，用其它方法易产生内存溢出时，深度优先搜索不失为一种有效的求解方法。 广度优先搜索算法，一般需存储产生的所有结点，占用的存储空间要比深度优先搜索大得多，因此，程序设计中，必须考虑溢出和节省内存空间的问题。但广度优先搜索法一般无回溯操作，即入栈和出栈的操作，所以运行速度比深度优先搜索要快些。

本文来源：https://www.bwwdw.com/article/wv5j.html