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