程序设计：深度优先搜索算法.doc

深度优先搜索算法教程[例1]有A、B、C、D、E五本书，要分给张、王、刘、赵、钱五位同学，每人只能选一本。事先让每个人将自己喜爱的书填写在下表中。希望你设计一个程序，打印分书的所有可能方案，当然是让每个人都满意。（如下图所示）HYPERLINK"http://www.kangjiezx.net/jingsai/uploadfile/jpg/2008-4/2008418112847265.jpg"\o"点击图片看全图"\t"_blank"[分析]这个问题中喜爱的书是随机的，没有什么规律，所以用穷举法比较合适。为编程方便，用1、2、3、4、5分别表示这五本书。这五本书的一种全排列就是五本书的一种分法。例如54321表示第5本书（即E）分给张，第4本书（即D分给王，）……第1本书（即A分给钱）。“喜爱书表”可以用二维数组来表示，1表示喜爱，0表示不喜爱。[算法设计]：产生5个数字的一个全排列；检查是否符合“喜爱书表”的条件，如果符合就打印出来。检查是否所有排列都产生了，如果没有产生完，则返回1。结束。[算法改进]：因为张只喜欢第3、4本书，这就是说，1****一类的分法都不符合条件。所以改进后的算法应当是：在产生排列时，每增加一个数，就检查该数是否符合条件，不符合，就立即换一个，符合条件后，再产生下一个数。因为从第i本书到第i+1本书的寻找过程是相同的，所以可以用递归算法。算法如下：proceduretry(i);{给第I个同学发书}beginforj:=1to5dobeginif第i个同学分给第j本书符合条件thenbegin记录第i个数;{即j值}ifi=5then打印一个解elsetry(i+1);删去第i个数字endendend;具体如下：◆递归算法programzhaoshu;constlike:array[1..5,1..5]of0..1=((0,0,1,1,0),(1,1,0,0,1),(0,1,1,0,0),(0,0,0,1,0),(0,1,0,0,1));name:array[1..5]ofstring[5]=('zhang','wang','liu','zhao','qian');varbook:array[1..5]of0..5;flag:setof1..5;c:integer;procedureprint;vari:integer;begininc(c);writeln('answer',c,':');fori:=1to5dowriteln(name[i]:10,':',chr(64+book[i]));end;proceduretry(i:integer);varj:integer;beginforj:=1to5doifnot(jinflag)and(like[i,j]>0)thenbeginflag:=flag+[j];book[i]:=j;ifi=5thenprintelsetry(i+1);flag:=flag-[j];book[i]:=0;end;end;{=====main====}beginflag:=[];c:=0;try(1);readln;end.C语言代码：#include<stdio.h>#include<stdlib.h>intlike[5][5]={0,0,1,1,0,1,1,0,0,1,0,1,1,0,0,0,0,0,1,0,0,1,0,0,1};charname[5][10]={"zhang","wang","liu","zhao","qian"};intflag[5]={1,1,1,1,1};intbook[5],c=0;voidprint(){inti;c++;printf("answer%d:",c);for(i=0;i<=4;i++)printf("%s:%c",name[i],65+book[i]);printf("\n");}voiddsf(inti){intj;for(j=0;j<=4;j++)if(flag[j]&&like[i][j]){flag[j]=0;book[i]=j;if(i==4)print();elsedsf(i+1);flag[j]=1;book[i]=0;}}intmain(){dsf(0);system("pause");return0;}◆非递归算法programpath;dep:=0;{dep为栈指针，也代表层次}repeatdep:=dep+1;r:=0;p:=false;repeatr:=r+1;if子节点mr符合条件then产生新节点并存于dep指向的栈顶；if子节点是目标then输出并退出（或退栈）elsep:=true;elseifr>=maxrthen回溯elsep:=flase;endif;untilp:=true;