ACM算法设计-BFS广度搜索-DFS入门深度搜索详解省名师优质课获奖课件市赛课一等奖课件.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,本幻灯片资料仅供参考，不能作为科学依据，如有不当之处，请参考专业资料。谢谢,ACM算法设计BFS(广度搜索)-DFS(深度搜索)详解,第1页,BFS算法,by plato,第2页,复习,DFS,算法,思想：一直往深处走，直到找到解或者走不下去为止,框架：,DFS(dep,)/dep,代表当前,DFS,深度,if(,找到解,|,走不下去了,),return;,枚举下一个情况，,DFS(dep+1,),第3页,3,DFS,遍历方式,H,A,L,I,F,B,C,D,E,J,G,K,S,第4页,4,存在其它遍历方式？,第5页,5,BFS,思想,1.,从初始状态,S,开始，利用规则，生成下一层状态。,2.,次序检验下一层全部状态，看是否出现目标状态,G,。,否则就对该层全部状态节点，分别利用规则。生成再下一层全部状 态节点。,3.,继续按上面思想生成再下一层全部状态节点，这么一层一层往下展开。直到出现目标状态为止。,按层次次序来遍历搜索树,第6页,6,BFS,框架,通惯用队列,(,先进先出,FIFO),实现,初始化队列,Q.,Q=,起点,s;,标识,s,为己访问,;,while(Q,非空,),取,Q,队首元素,u;u,出队,;,if(u=,目标状态,),全部与,u,相邻且未被访问点进入队列,;,标识,u,为已访问,;,第7页,7,8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,入口,出口,寻找一条从入口到出口通路,迷宫问题,第8页,8,东,南,北(,上,),西(,左,),前进方向：上(北)、下(南)、左(西)、右(东),首先从下方开始，按照逆时针方向搜索下一步可能前进位置,迷宫问题,-DFS,第9页,9,入口,出口,在迷宫周围加墙，防止判断是否出界,8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,迷宫问题,-DFS,第10页,10,8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,在寻找出口过程中，每前深入，当前位置入栈；每回退一步，栈顶元素出栈,栈,(1,1),迷宫问题,-DFS,第11页,11,i,8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,栈,(1,1),(2,1),向下方前深入,迷宫问题,-DFS,第12页,12,i,8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,栈,(1,1),(2,1),i,(3,1),向下方前深入,迷宫问题,-DFS,第13页,13,i,i,8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,栈,(1,1),(2,1),(4,1),(3,1),i,向下方前深入,break,迷宫问题,-DFS,第14页,14,i,i,i,i,8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,栈,(1,1),(2,1),(5,1),(3,1),(4,1),向下方前深入,break,迷宫问题,-DFS,第15页,15,i,i,i,i,i,8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,栈,(1,1),(2,1),(6,1),(3,1),(4,1),(5,1),向下方前深入,break,迷宫问题,-DFS,第16页,16,i,i,i,i,i,i,迷宫问题(续),8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,90,9,0,栈,(1,1),(2,1),(7,1),(3,1),(4,1),(5,1),(6,1),向下方前深入,break,第17页,17,i,i,i,i,i,i,8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,向下方、右方、左方均不能前进，上方是来路，则后退,栈,(1,1),(2,1),(7,1),(3,1),(4,1),(5,1),(6,1),break,迷宫问题,-DFS,第18页,18,i,i,i,i,i,8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,栈,(1,1),(2,1),(3,1),(4,1),(5,1),(6,1),向右方、左方均不能前进，下方路不通，上方是来路，则后退,break,迷宫问题,-DFS,第19页,19,i,i,i,i,i,8,1,2,3,4,5,6,7,0,9,8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,栈,(1,1),(2,1),(3,1),(4,1),(5,1),(5,2),向右方前深入,break,迷宫问题,-DFS,第20页,20,i,i,i,i,i,i,8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,下方路不通，向右方前深入,栈,(1,1),(2,1),(3,1),(4,1),(5,1),(5,3),(5,2),break,迷宫问题,-DFS,第21页,21,i,i,i,i,i,i,i,8,1,2,3,4,5,6,7,0,9,8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,向下方前深入,栈,(1,1),(2,1),(3,1),(4,1),(5,1),(6,1),(5,2),(5,3),break,迷宫问题,-DFS,第22页,22,i,i,i,i,i,i,i,8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,下方路不通，向右方前深入,栈,(1,1),(2,1),(3,1),(4,1),(5,1),(6,4),(5,2),(5,3)6,3),i,break,迷宫问题,-DFS,第23页,23,i,i,i,i,i,i,i,i,i,8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,下方路不通，向右方前深入,栈,(1,1),(2,1),(3,1),(4,1),(5,1),(6,5),(5,2),(5,3),(6,3),(6,4),break,迷宫问题,-DFS,第24页,24,i,i,i,i,i,i,i,i,i,i,8,1,2,3,4,5,6,7,0,9,8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,向下方前深入,栈,(1,1),(2,1),(3,1),(4,1),(5,1),(7,5),(5,2),(5,3),(6,3),(6,4),(6,5),break,迷宫问题,-DFS,第25页,25,i,i,i,i,i,i,i,i,i,i,i,8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,向下方前深入,栈,(1,1),(2,1),(3,1),(4,1),(5,1),(8,5),(5,2),(5,3),(6,3),(6,4),(6,5),(7,5),break,迷宫问题,-DFS,第26页,26,i,i,i,i,i,i,i,i,i,i,i,i,8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,下方路不通，向右方前深入,栈,(1,1),(2,1),(3,1),(4,1),(5,1),(8,6),(5,2),(5,3),(6,3),(6,4),(6,5),(7,5),(8,5),break,迷宫问题,-DFS,第27页,27,i,i,i,i,i,i,i,i,i,i,i,i,i,8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,下方路不通，向右方前深入,栈,(1,1),(2,1),(3,1),(4,1),(5,1),(8,7),(5,2),(5,3),(6,3),(6,4),(6,5),(7,5),(8,5),(8,6),break,迷宫问题,-DFS,第28页,28,i,i,i,i,i,i,i,i,i,i,i,i,8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,下方路不通，向右方前深入，抵达出口,栈,(1,1),(2,1),(3,1),(4,1),(5,1),(8,8),(5,2),(5,3),(6,3),(6,4),(6,5),(7,5),(8,5),(8,6),i,i,(8,7),break,迷宫问题,-DFS,第29页,29,i,i,i,i,i,i,i,i,i,i,i,i,i,i,8,1,2,3,4,5,6,7,9,8,1,2,3,4,5,6,7,0,9,0,用栈保留了路径,栈,(1,1),(2,1),(31),(4,1),(5,1),(8,8),(5,2),(5,3),(6,3),(6,4),(6,5),(7,5),(8,5),(8,6),(8,7),迷宫问题,-DFS,第30页,30,入口,出口,借助于队列可求得入口到出口最短路径(若存在),8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,迷宫问题(最短路径),-BFS,第31页,31,1,1,入口,出口,借助于队列可求得入口到出口最短路径(若存在),8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,迷宫问题(最短路径),-BFS,第32页,32,1,1,2,2,入口,出口,借助于队列可求得入口到出口最短路径(若存在),8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,迷宫问题(最短路径),-BFS,第33页,33,1,1,2,2,3,3,入口,出口,借助于队列可求得入口到出口最短路径(若存在),8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,迷宫问题(最短路径),-BFS,第34页,34,1,1,2,2,3,4,3,4,入口,出口,借助于队列可求得入口到出口最短路径(若存在),8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,迷宫问题(最短路径),-BFS,第35页,35,11,2,2,3,4,5,3,4,5,5,入口,出口,借助于队列可求得入口到出口最短路径(若存在),8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,迷宫问题(最短路径),-BFS,第36页,36,1,1,2,6,2,3,4,5,3,4,5,6,5,6,入口,出口,借助于队列可求得入口到出口最短路径(若存在),8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,迷宫问题(最短路径),-BFS,第37页,37,1,7,1,2,6,7,2,3,4,5,3,4,5,6,5,7,6,入口,出口,借助于队列可求得入口到出口最短路径(若存在),8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,迷宫问题(最短路径),-BFS,第38页,38,1,7,8,1,2,6,7,8,2,3,4,5,3,4,5,6,5,7,8,6,入口,出口,借助于队列可求得入口到出口最短路径(若存在),8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,迷宫问题(最短路径),-BFS,第39页,39,1,7,8,9,1,2,6,7,8,2,3,4,5,3,4,5,6,5,7,8,9,6,入口,出口,借助于队列可求得入口到出口最短路径(若存在),8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,9,迷宫问题(最短路径),-BFS,第40页,40,1,7,8,9,1,2,6,7,8,2,3,4,5,10,3,10,4,5,6,10,5,7,8,9,6,10,入口,出口,借助于队列可求得入口到出口最短路径(若存在),8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,9,迷宫问题(最短路径),-BFS,第41页,41,1,7,8,9,1,2,6,7,8,2,3,4,5,10,11,3,11,10,11,4,5,6,10,11,5,7,8,9,6,10,11,入口,出口,借助于队列可求得入口到出口最短路径(若存在),8,1,2,3,4,5,6,78,1,2,3,4,5,6,7,9,0,9,0,9,迷宫问题(最短路径),-BFS,第42页,42,1,7,8,9,1,2,6,7,8,12,2,3,4,5,10,11,3,11,10,11,12,4,5,6,10,11,12,5,7,8,9,6,10,12,11,12,入口,出口,借助于队列可求得入口到出口最短路径(若存在),8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,9,迷宫问题(最短路径),-BFS,第43页,43,1,7,8,9,13,1,2,6,7,8,12,2,3,4,5,10,11,3,11,10,11,12,4,5,6,10,11,12,13,5,7,8,9,6,10,13,12,11,12,13,入口,出口,借助于队列可求得入口到出口最短路径(若存在),8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,9,迷宫问题(最短路径),-BFS,第44页,44,1,7,8,9,13,1,2,6,7,8,12,2,3,4,5,10,11,3,11,10,11,12,4,5,6,10,11,12,13,5,7,8,9,6,10,13,12,11,12,13,入口,出口,借助于队列可求得入口到出口最短路径(若存在),8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,9,迷宫问题(最短路径),-BFS,第45页,45,小结,DFS,：使用,栈,保留未被检测结点，结点按照,深度优先,次序被访问并依次被压入栈中，并以相反次序出栈进行新检测。,类似于树先根遍历,深搜例子：走迷宫，你没有方法用分身术来站在每个走过位置。不撞南山不回头,。,BFS,：使用,队列,保留未被检测结点。结点按照,宽度优先,次序被访问和进、出队列。,类似于树按层次遍历过程,广搜例子,:,你眼镜掉在地上以后，你趴在地板上找。你总是先摸最靠近你地方，假如没有，再摸远一点地方,第46页,46,例题,2,Oil Deposits,题意：给出一个,N,*,M,矩形区域和每个区域状态,-,有,/,没有石油，（定义）假如两个有石油区域是相邻（水平、垂直、斜）则认为这是属于同一个,oil pocket,。,求这块矩形区域一共有多少,oil pocket,。,第47页,47,思绪：,对于每个有油区域，找出全部与它同属一个,oil pocket,有油区域，最终计算一共有多少个,oil pocket,。,？怎样去找出全部与它同属一个,oil pocket,BFS,：找到一个起点；,从这个点出发，枚举四面寻找有油区域；,顺序从找到新区域出发，循环上述过程，直到没有新区域加入。,？怎样去标志同属一个,oil pocket,有油区域,设置一个访问标志代表此区域有没有被包含过，这么话调用,BFS,次数就,=oil pocket,数目。,当然,DFS,也是能够这么做。,FloodFill,第48页,48,框架：,Void BFS(int i,int j),初始化队列,Q,；,while(Q,不为空）,取出队首元素,u;,枚举元素,u,相邻区域，,if(,此区域有油,),入队,;,访问标识,;,Int main(),枚举全部区域，,if(,此区域有油,&,没有被访问过,),BFS(,),第49页,49,练习,:8080/judge/contest/view.action?cid=17535#overview,密码：,123456,第50页,50,推荐书籍,第51页,51,