《广度优先搜索教案》由会员分享，可在线阅读，更多相关《广度优先搜索教案（46页珍藏版）》请在金锄头文库上搜索。
1、1/31广度优先搜索 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life, there is hope。有生命必有希望。有生命必有希望2/31广度优先搜索算法（广度优先搜索算法（Breadth-First-Search）也被作宽度优先搜索，或横向优先搜索，简称也被作宽度优先搜索，或横向优先搜索，简称BFS。BFS是从是从根节点根节点开始，沿着树的宽度遍历树的开始，沿着树的宽度遍历树的节点节点。如果所有。如果所有节点均被访问，则算法中止。节点均被访问，则算法中止。广度优先搜索的实现一般采用队列。所有因为展开节点而广度优先搜索的实
2、现一般采用队列。所有因为展开节点而得到的子节点都会被加进一个得到的子节点都会被加进一个先进先出先进先出的队列中的队列中。因为所有节点都必须被储存，因此因为所有节点都必须被储存，因此BFS的空间复杂度为的空间复杂度为O(|V|+|E|)，其中，其中|V|是节点的数目，而是节点的数目，而|E|是图中边的数是图中边的数目。目。另一种说法称另一种说法称BFS的空间复杂度为的空间复杂度为O(BM)，其中，其中B是最大是最大分支系数，而分支系数，而M是树的最长路径长度。由于对空间的大量是树的最长路径长度。由于对空间的大量需求，因此需求，因此BFS并不适合解非常大的问题。并不适合解非常大的问题。最差情形下，
3、最差情形下，BFS必须寻找所有到可能节点的所有路径，必须寻找所有到可能节点的所有路径，因此其时间复杂度为因此其时间复杂度为O(|V|+|E|)，其中，其中|V|是节点的数目，是节点的数目，而而|E|是图中边的数目。是图中边的数目。 3/31还是以迷宫作为引入。可怜的小老鼠被困在了迷宫里面想还是以迷宫作为引入。可怜的小老鼠被困在了迷宫里面想要逃出去，但是它不知道到底该怎么走，无论如何还是先要逃出去，但是它不知道到底该怎么走，无论如何还是先选定一个方向走一下再说。选定一个方向走一下再说。我们对各个方向设定一个优先级，比如我们设定先向上走，我们对各个方向设定一个优先级，比如我们设定先向上走，再向右走
4、，然后是向下，向左。这个顺序是顺时针排的。再向右走，然后是向下，向左。这个顺序是顺时针排的。不难相当，通过设定一个优先级，我们可以保证在行进过不难相当，通过设定一个优先级，我们可以保证在行进过程不会因为随机选择而出现重复情况。程不会因为随机选择而出现重复情况。深度优先搜索的思路是找到一条可能的路就一直那么走下深度优先搜索的思路是找到一条可能的路就一直那么走下去只到走不通为止。这个走不通可能的情况很多，也许是去只到走不通为止。这个走不通可能的情况很多，也许是遇到了自然的障碍物，也就是到了死胡同走不下去了，这遇到了自然的障碍物，也就是到了死胡同走不下去了，这个时侯只有倒退回去。个时侯只有倒退回去。
5、但是现实总是充满了陷阱。或许就存在这么一种路，当你但是现实总是充满了陷阱。或许就存在这么一种路，当你辛辛苦苦走了几十步甚至上百步之后才发现那是一个没有辛辛苦苦走了几十步甚至上百步之后才发现那是一个没有未来的选择。我们可以在迷宫中给老鼠设定，上帝也可以未来的选择。我们可以在迷宫中给老鼠设定，上帝也可以在人生里为我们设定。在人生里为我们设定。 4/31我们发现固执的小老鼠就是那样子走下去了没有我们发现固执的小老鼠就是那样子走下去了没有回头。该怎么办才能防止这种情况的发生呢？回头。该怎么办才能防止这种情况的发生呢？对，我们可以叫住他！对，我们可以叫住他！“喂，那条路不能走了，喂，那条路不能走了，快回
6、来！快回来！”实现起来其实很简单，就是在程序里实现起来其实很简单，就是在程序里面加一个深度判断，如果深度达到了一个上界，面加一个深度判断，如果深度达到了一个上界，我们就不继续往下走了，也就是跳出返回。其实我们就不继续往下走了，也就是跳出返回。其实这里面要涉及的还有很多，比如迭代加深搜索，这里面要涉及的还有很多，比如迭代加深搜索，A*等。等。其实我们可以让那只老鼠变得聪明一点的。假如其实我们可以让那只老鼠变得聪明一点的。假如我们的主角不是一只小老鼠，而是一大群，如果我们的主角不是一只小老鼠，而是一大群，如果你是老鼠王，你会怎么安排让你的子民们尽快逃你是老鼠王，你会怎么安排让你的子民们尽快逃生？生
7、？Thinking。5/31很简单，让老鼠们分头行动。我们给每一只老鼠很简单，让老鼠们分头行动。我们给每一只老鼠都配一个对讲机。从出发点开始分成四个小队，都配一个对讲机。从出发点开始分成四个小队，四个小队分别分别负责四个方向，一起出发。每四个小队分别分别负责四个方向，一起出发。每次只能选择没有去过的地方走，没有去过既包括次只能选择没有去过的地方走，没有去过既包括自己没有去过也要包括别的老鼠没有去过，这个自己没有去过也要包括别的老鼠没有去过，这个我们可以用一个布尔数组在去过的地方标记一下，我们可以用一个布尔数组在去过的地方标记一下，对于小老鼠来说标记的方式可能会比较特殊。每对于小老鼠来说标记的方
8、式可能会比较特殊。每次到一个位置都可能会有几种不同的走法，那好，次到一个位置都可能会有几种不同的走法，那好，我们把当前的这个小队再次划分，每个能走的方我们把当前的这个小队再次划分，每个能走的方向都派一个小小队去。如果没有路可走了，就呆向都派一个小小队去。如果没有路可走了，就呆在那儿了。当有一队老鼠或者是一只找到了出口，在那儿了。当有一队老鼠或者是一只找到了出口，这位英雄就在对讲机里大吼一声，这位英雄就在对讲机里大吼一声，“哈哈，我找哈哈，我找到出口啦，大家到这里来到出口啦，大家到这里来”。6/31相信大家听问题的时候都注意到了关键词相信大家听问题的时候都注意到了关键词“尽快尽快”。毋庸置疑，老
9、鼠们的做法是肯定能在最快时。毋庸置疑，老鼠们的做法是肯定能在最快时间内找到出口。接下来我们分析一下其中原因。间内找到出口。接下来我们分析一下其中原因。我们给老鼠能到的每个方块一个距离。初始位置我们给老鼠能到的每个方块一个距离。初始位置的距离为的距离为0，由这个位置出发能到的距离为，由这个位置出发能到的距离为1，再，再有这些点能到的不重复的点的距离为有这些点能到的不重复的点的距离为2。如此。如此下去，我们就可以给每一个可以到达的位置一个下去，我们就可以给每一个可以到达的位置一个距离值。我们每次所做的都是把一个位置能够拓距离值。我们每次所做的都是把一个位置能够拓展的所有位置都拓展出来了，而且也没有
10、走重复展的所有位置都拓展出来了，而且也没有走重复的路。可以保证在到达某一个位置的时候我们所的路。可以保证在到达某一个位置的时候我们所走的距离肯定是最短的。走的距离肯定是最短的。这就是宽度优先搜索。这就是宽度优先搜索。恭喜老鼠们成功获救！可是现在的问题我们如何恭喜老鼠们成功获救！可是现在的问题我们如何在程序里面实现？在程序里面实现？7/31BFS的关键：队列的关键：队列我们要模拟出小老鼠找路的过程就必须把每一个我们要模拟出小老鼠找路的过程就必须把每一个时刻每一队小老鼠所到的位置记录下来。对于我时刻每一队小老鼠所到的位置记录下来。对于我们来说，只有在知道当前老鼠的位置的前提下，们来说，只有在知道当
11、前老鼠的位置的前提下，我们才能产生下一时间的决策。而为了达到上面我们才能产生下一时间的决策。而为了达到上面所说的拓展最短，我们就必须根据各个位置被到所说的拓展最短，我们就必须根据各个位置被到达的先后顺序来拓展。这就要用到队列。达的先后顺序来拓展。这就要用到队列。 我们把每一个到的位置叫做一个状态。象这样子我们把每一个到的位置叫做一个状态。象这样子来构造一个队列。最初队列里只有一个元素，那来构造一个队列。最初队列里只有一个元素，那就是最初的状态。机器开始运行了。第一次我们就是最初的状态。机器开始运行了。第一次我们从队列里面取出第一个元素。然后对它进行拓展，从队列里面取出第一个元素。然后对它进行拓
12、展，找到所有由它为基础能到的状态，然后我们把这找到所有由它为基础能到的状态，然后我们把这些状态加入到队列里面。这样的操作不断重复，些状态加入到队列里面。这样的操作不断重复，直到我们找到了我们想要的为止。当然操作不止直到我们找到了我们想要的为止。当然操作不止这么简单。我们还必须对过去已经到过的进行标这么简单。我们还必须对过去已经到过的进行标记。记。 8/31另外，我们可以通过在状态之中添加一些信息而实现更多的东西，比如路径保存，方向记录等。这样我们就可以实现BFS了。参考结构见下(伪代码)Q0,QNum=1;/初始队列元素设定，初始队列元素设定，QNum用于存储队列元素个数用于存储队列元素个数I
13、=0;/指针指向队列首位指针指向队列首位While(IQNum)/拓展拓展QI；QNum可能会变化可能会变化I+；/指针后移指针后移9/31以以德国德国城市为范例的地图，城市为范例的地图，城市间有数条道路相连接。城市间有数条道路相连接。从法兰克福法兰克福开始执行广度开始执行广度优先搜索算法，所产生的优先搜索算法，所产生的广度优先搜索算法树。广度优先搜索算法树。10/311、首先将根节点放入队列中。 2、从队列中取出第一个节点，并检验它是否为目标。 如果找到目标，则结束搜寻并回传结果。 否则将它所有尚未检验过的直接子节点加入队列中。 3、若队列为空，表示整张图都检查过了亦即图中没有欲搜寻的目标。
14、结束搜寻并回传“找不到目标”。 4、重复步骤2。 11/31算法：算法： voidBFS(VLinkG,intv)intw;VISIT(v);/*访问顶点访问顶点v*/visitedv=1;/*顶点顶点v对应的访问标记置为对应的访问标记置为1*/ADDQ(Q,v);while(!QMPTYQ(Q)v=DELQ(Q);/*退出队头元素退出队头元素v*/w=FIRSTADJ(G,v);/*求求v的第的第1个邻接点。无邻接点则返回个邻接点。无邻接点则返回-1*/while(w!=-1)if(visitedw=0)VISIT(w);/*访问顶点访问顶点v*/ADDQ(Q,w);/*当前被访问的顶点当前
15、被访问的顶点w进队进队*/visitedw=1;/*顶点顶点w对应的访问标记置为对应的访问标记置为1*/W=NEXTADJ(G,v);/*求求v的下一个邻接点。若无邻接点的下一个邻接点。若无邻接点则返回则返回-1*/12/31总结总结BFS的思路就是第的思路就是第N步就把步就把N步所能达到的所步所能达到的所有状态都找出来。当然这样子是有代价的，那就有状态都找出来。当然这样子是有代价的，那就是可能需要比是可能需要比DFS多很多的空间。不过多很多的空间。不过BFS的优的优势在于它能够很快的找到最优解。势在于它能够很快的找到最优解。BFS和和DFS一一样都是很暴力的算法，因为它们都属于盲目搜索样都是
16、很暴力的算法，因为它们都属于盲目搜索算法。算法。13/31FindTheMultiplehttp:/ Foreachvalueofnintheinputprintalinecontainingthecorrespondingvalueofm.Thedecimalrepresentationofmmustnotcontainmorethan100digits.Iftherearemultiplesolutionsforagivenvalueofn,anyoneofthemisacceptable.15/31SampleInput26190 SampleOutput1010010010010010
17、0100111111111111111111 16/31这等同于构造一颗二叉树，然后按层次去遍历这颗树；1101110010111011117/31#includeusingnamespacestd;intn;longlongq9999999;intmain()while(scanf(%d,&n)&n)BFS();return0;18/31voidBFS()intfront,rear;front=rear=0;qrear=1;rear+;longlongtop;while(rearfront)top=qfront;if(top%n=0)break;top*=10;qrear+=top;qrea
18、r+=top+1;front+;printf(%lldn,top);19/31PrimePathhttp:/ 20/31Now,theministeroffinance,whohadbeeneavesdropping,intervened.Nounnecessaryexpenditure,please!Ihappentoknowthatthepriceofadigitisonepound.Hmm,inthatcaseIneedacomputerprogramtominimizethecost.Youdontknowsomeverycheapsoftwaregurus,doyou?Infact,
19、Ido.Yousee,thereisthisprogrammingcontestgoingon.Helptheprimeministertofindthecheapestprimepathbetweenanytwogivenfour-digitprimes!Thefirstdigitmustbenonzero,ofcourse.Hereisasolutioninthecaseabove.1033173337333739377987798179Thecostofthissolutionis6pounds.Notethatthedigit1whichgotpastedoverinstep2cann
20、otbereusedinthelaststepanew1mustbepurchased.21/31InputOnelinewithapositivenumber:thenumberoftestcases(atmost100).Thenforeachtestcase,onelinewithtwonumbersseparatedbyablank.Bothnumbersarefour-digitprimes(withoutleadingzeros).OutputOnelineforeachcase,eitherwithanumberstatingtheminimalcostorcontainingt
21、hewordImpossible.22/31SampleInput3103381791373801710331033 SampleOutput670 23/31首先区分首先区分theprimeminister和和primenumber中的中的prime的不同意思。的不同意思。从起始素数开始进行广搜，每轮将所有可行的改从起始素数开始进行广搜，每轮将所有可行的改变（个位至千位，每个位置进行一次改变）放入变（个位至千位，每个位置进行一次改变）放入搜寻队列一次进行素数判断。搜寻队列一次进行素数判断。 用数组来记载转变路径，每个结点指向其父结点。用数组来记载转变路径，每个结点指向其父结点。达到纲标之后向
22、上寻找到先人，即可求出转变了达到纲标之后向上寻找到先人，即可求出转变了多少次多少次 。24/31STL：queue#include定义一个定义一个queue的变量的变量queueM查看是否为空队列查看是否为空队列M.empty()是的话返回是的话返回1，不是返回，不是返回0;从已有元素后面增加元素从已有元素后面增加元素M.push()输出现有元素的个数输出现有元素的个数M.size()显示第一个元素显示第一个元素M.front()显示最后一个元素显示最后一个元素M.back()清除第一个元素清除第一个元素M.pop()25/31#include#include#includeusingname
23、spacestd;inta,b;intp9999=0;intvisited9999=0;boolisprime(intx)for(inti=2;i=sqrt(double)x);+i)if(x%i=0)returnfalse;returntrue;26/31intBFS(ints,intr)queueq;q.push(s);ps=0;visiteds=1;while(!q.empty()inttemp=q.front();q.pop();for(inti=0;i=9;i+)inty1=(temp/10)*10+i;if(isprime(y1)&!visitedy1)q.push(y1);py1
24、=ptemp+1;visitedy1=1;inty2=temp%10+(temp/100)*100+i*10;if(isprime(y2)&!visitedy2)q.push(y2);py2=ptemp+1;visitedy2=1;27/31inty3=temp%100+(temp/1000)*1000+100*i;if(isprime(y3)&!visitedy3)q.push(y3);py3=ptemp+1;visitedy3=1;if(i!=0)inty4=temp%1000+i*1000;if(isprime(y4)&!visitedy4)q.push(y4);py4=ptemp+1;
25、visitedy4=1;if(visitedr)returnpr;return0;28/31intmain()intn;scanf(%d,&n);while(n-)memset(visited,0,sizeof(visited);memset(p,0,sizeof(p);scanf(%d%d,&a,&b);printf(%dn,BFS(a,b);return0;29/31Erdos Number http:/ DescriptionPaulErdos(1913-1996)isalegendarymathematicianofthe20thcentury.Famousforhiseccentri
26、clivingstyle,Erdoswasoneofthemostprolificpublishersofpapersinmathematicalhistory,havingwrittenaround1500mathematicalarticles,mostlywithco-authors.Erdosspentmostofhislifetimetravelingbetweenscientificconferencesandvisitinghomesofcolleaguesallovertheworld,withmostofhisbelongingsinasuitcase.Hewouldtypi
27、callyshowupatacolleaguesdoorstepandannouncemybrainisopen,stayinglongenoughtocollaborateonafewpapersbeforemovingonafewdayslater.Inmanycases,hewouldaskthecurrentcollaboratorwhomheshouldvisitnext.Becauseofhisprolificoutput,friendscreatedtheErdosnumberasahumoroustribute,whichhasbeenapartofthefolkloreofm
28、athematiciansthroughouttheworldformanyyears.ErdoshimselfisassignedtheErdosnumberof0. 30/31Thosewhohaveco-writtenapaperwithErdoshaveanErdosnumberof1.Inturn,authorswhohavecollaboratedwiththosewhoseErdosnumberis1(butnotwithErdoshimself)haveanErdosnumberof2.Ingeneral,ifthelowestErdosnumberofthecowriters
29、ofanauthorisS,thenhisErdosnumberisS+1.ApersonwithnosuchcoauthorshipchainconnectingtoErdoshasaninfiniteErdosnumber.Forexample,inthepictureabove,theladycollaborateswithErdosononepaper,andthenwiththemanontherightonanother,sothismanisgivenanErdosnumberof2(assuminghehasnevercollaboratedwithErdoshimself).
30、31/31TheinterestingthingwithErdosnumberisthatabout90%oftheworldsactivemathematicianshaveanErdosnumbersmallerthan8,andmanymathematicianshaveanErdosnumbersurprisinglysmallerthantheyexpect.Forexample,AndrewWiles,whohaveprovedtheFermatsLastTheoremandwhoseresearchareaisverydifferentfromthatofErdos,hasanE
31、rdosnumberofonly3.AllFieldsprizewinnershaveanErdosnumberatmost5andallWolfprizewinnersErdosnumbersdonotexceed6.Inaddition,averylargenumberofnon-mathematiciansalsohavefiniteErdosnumbers.Forexample,AlbertEinsteinhasanErdosnumberof2andBillGateshasanErdosnumberof4.Yourtaskis,givenalistofco-writingactivit
32、iesofauthors,toansweraseriesofqueriesaccordingtothelist,whichhavetheform:WhatistheErdosnumberofauthorA?32/31InputThefirstlineoftheinputfileisanintegerN,numberofco-authoringactivities.ThenextNlineseachcontaintwonames,separatedwithspaces,meaningthesetwoauthorshaveco-writtenapaper.Onthenextlineisaninte
33、gerM,numberofqueries.ThenextMlineseachcontainthenameofanauthor. Constraints N 50000, M 5000033/31NotesNamescontainletters(A-Z,a-z)and.onlyanddontcontainwhitespaces.Eachnamehasatmost20characters.Namesarecase-sensitive,e.g.Erdosisnotthesamepersonaserdos.Authorswiththesamenameshouldbeconsideredthesamep
34、erson.PaulErdoshimselfisrepresentedwithexactlythenameErdos.Thesameco-authoringactivityislistedatmostonce.Noauthorwillbeco-authoringwithhimself.34/31OutputForeachquery,outputthecorrespondingauthorsErdosnumberonaline.IftheauthordoesnthaveafiniteErdosnumber,outputinfinityinstead(quotesforclarityonly).
35、35/31SampleInput7ErdosAndrew.OdlyzkoAndrew.OdlyzkoChris.M.SkinnerChris.M.SkinnerAndrew.WilesErdosPavol.HellPavol.HellXiao.Tie.DengXiao.Tie.DengChris.PapadimitriouChris.PapadimitriouBill.Gates3Andrew.WilesBill.GatesAlbert.Einstein SampleOutput34infinity 36/31以以Erdos为起始点直接为起始点直接BFS扩展一棵宽度优扩展一棵宽度优先树，两个节
36、点有边当且仅当这两个作者先树，两个节点有边当且仅当这两个作者合作。合作。每个节点在树中到每个节点在树中到Erdos的距离就是它的的距离就是它的Erdos数。数。陷阱：输入的合作关系里边可能没有陷阱：输入的合作关系里边可能没有Erdos这个人，但是查询中可能会有这个人，但是查询中可能会有Erdos，这时，这时应当输出应当输出0而不是而不是infinity。37/31为了迅速的找到为了迅速的找到Erdos，可构造经典的字符串，可构造经典的字符串Hash函数实现。函数实现。unsignedELFhash(constchar*key)unsignedh=0;while(*key!=0)h=(h24;h
37、&=g;returnh%HASH_SCALE;38/31#include#include#includeconstunsignedMAX_LEN=20;constunsignedHASH_SCALE=400000;structNodecharnameMAX_LEN+1;int dist;Node*next;std:listneib;Node(constchar_name,Node*_next):dist(-1),next(_next)strcpy(name,_name);39/31Node*hashTableHASH_SCALE;unsignedELFhash(constchar*key)un
38、signedh=0;while(*key!=0)h=(h24;h&=g;returnh%HASH_SCALE;Node*enhash(constcharname)unsignedh=ELFhash(name);Node*p=hashTableh;while(p!=NULL&strcmp(p-name,name)!=0)p=p-next;returnp?p:hashTableh=newNode(name,hashTableh);40/31voidbfs() std:queueQ;Q.push(enhash(Erdos);Q.front()-dist=0;while(!Q.empty()typed
39、efstd:list:iterator IP;intd=Q.front()-dist+1;std:list&L=Q.front()-neib;Q.pop();for(IPp=L.begin();p!=L.end();p+)if(*p)-dist=-1)Q.push(*p);(*p)-dist=d;41/31voidget_coauthor_activities()intN;scanf(%d,&N);while(N-)charname1MAX_LEN+1,name2MAX_LEN+1;Node*p,*q;scanf(%s%s,name1,name2);p=enhash(name1);q=enha
40、sh(name2);p-neib.push_back(q);q-neib.push_back(p);42/31voiddo_query() intM;scanf(%d,&M);while(M-)charnameMAX_LEN+1;intd;scanf(%s,name);d=enhash(name)-dist;if(d!=-1)printf(%dn,d);elseputs(infinity);intmain() get_coauthor_activities();bfs();do_query();43/31作业练习题：作业练习题：http:/ 倒水问题倒水问题 1、问题描述、问题描述有装满水的有
41、装满水的6升的杯子、空的升的杯子、空的3升杯子和升杯子和1升杯子，升杯子，3个杯子中都个杯子中都没有刻度。在不使用其他道具的情况下，是否可以量出没有刻度。在不使用其他道具的情况下，是否可以量出4升的升的水呢？水呢？方法如下图所示：方法如下图所示：即，倒水问题的一种方法为：即，倒水问题的一种方法为：(6,0,0)(3,3,0)(3,2,1)(4,2,0)45/31倒水问题倒水问题 注意：由于没有刻度，用杯子注意：由于没有刻度，用杯子x给杯子给杯子y倒水时必须一直把杯子倒水时必须一直把杯子y倒满或者把杯子倒满或者把杯子x倒空，而不能中途停止。倒空，而不能中途停止。你的任务是解决一般性的问题：设大、
42、中、小你的任务是解决一般性的问题：设大、中、小3个杯子的容量个杯子的容量分别为分别为a,b,c，最初只有大杯子装满水，其他两个杯子为空。最，最初只有大杯子装满水，其他两个杯子为空。最少需要多少步才能让某一个杯子中的水有少需要多少步才能让某一个杯子中的水有x升呢？你需要打印升呢？你需要打印出每步操作后各个杯子中的水量出每步操作后各个杯子中的水量(0cba1000)。46/31倒水问题倒水问题 分析：分析：假设在某一时刻，大杯子中有假设在某一时刻，大杯子中有v0升水，中杯子中有升水，中杯子中有v1升水，小升水，小杯子中有杯子中有v2升水，我们称这时的系统状态为升水，我们称这时的系统状态为(v0,v1,v2)。把状。把状态想象成图的结点，可以得到上面例子中的状态图。态想象成图的结点，可以得到上面例子中的状态图。(6,0,0)(3,3,0)(5,0,1)(2,3,1)(5,1,0)(3,2,1)(4,2,0)(4,1,1)
