ACM算法设计-BFS(广度搜索)-DFS入门(深度搜索)详解课件.ppt

1、2022-11-14ACM算法设计BFS(广度搜索)-DFS(深度搜索)详解BFS算法 by plato3复习复习DFS算法算法思想：一直往深处走，直到找到解或者走不下去为止框架：DFS(dep,)/dep代表目前DFS的深度 if(找到解|走不下去了)return;枚举下一种情况，DFS(dep+1,)4DFS的遍历方式HALIFBCDEJGKS5存在其他的遍历方式？6BFS的思想1.从初始状态S开始，利用规则，生成下一层的状态。2.顺序检查下一层的所有状态，看是否出现目标状态G。否则就对该层所有状态节点，分别利用规则。生成再下一层的所有状 态节点。3.继续按上面思想生成再下一层的所有状态节

2、点，这样一层一层往下展开。直到出现目标状态为止。按层次的顺序来遍历搜索树7BFS框架通常用队列(先进先出,FIFO)实现初始化队列Q.Q=起点s;标记s为己访问;while(Q非空)取Q队首元素u;u出队;if(u=目标状态)所有与u相邻且未被访问的点进入队列;标记u为已访问;88123456781234567入口入口出口出口 寻找一条从入口到出口的通路寻找一条从入口到出口的通路迷宫问题9东南北(上上)西(左左)前进方向：上前进方向：上(北北)、下、下(南南)、左、左(西西)、右、右(东东)n首先从下方开始，按照逆时针方向搜索下一步首先从下方开始，按照逆时针方向搜索下一步可能前进的位置可能前进

3、的位置迷宫问题-DFS10入口出口 在迷宫周围加墙，避免判断是否出界在迷宫周围加墙，避免判断是否出界81234567812345679090迷宫问题-DFS1181234567812345679090 在寻找出口的过程中，每前进一步，当在寻找出口的过程中，每前进一步，当前位置入栈；每回退一步，栈顶元素出前位置入栈；每回退一步，栈顶元素出栈栈栈栈(1,1)(1,1)迷宫问题-DFS12i81234567812345679090栈栈(1,1)(1,1)(2,1)(2,1)向下方前进一步向下方前进一步迷宫问题-DFS13i81234567812345679090栈栈(1,1)(1,1)(2,1)(2

4、,1)i(3,1)(3,1)向下方前进一步向下方前进一步迷宫问题-DFS14ii81234567812345679090栈栈(1,1)(1,1)(2,1)(2,1)(4,1)(4,1)(3,1)(3,1)i 向下方前进一步向下方前进一步break迷宫问题-DFS15iiii81234567812345679090栈栈(1,1)(1,1)(2,1)(2,1)(5,1)(5,1)(3,1)(3,1)(4,1)(4,1)向下方前进一步向下方前进一步break迷宫问题-DFS16iiiii 81234567812345679090栈栈(1,1)(1,1)(2,1)(2,1)(6,1)(6,1)(3,1

5、)(3,1)(4,1)(4,1)(5,1)(5,1)向下方前进一步向下方前进一步break迷宫问题-DFS17iiiiii迷宫问题迷宫问题(续续)81234567812345679090栈栈(1,1)(1,1)(2,1)(2,1)(7,1)(7,1)(3,1)(3,1)(4,1)(4,1)(5,1)(5,1)(6,1)(6,1)向下方前进一步向下方前进一步break18iiiiii 81234567812345679090向下方、右方、左方均不能前进，上方是来路，则后退栈栈(1,1)(1,1)(2,1)(2,1)(7,1)(7,1)(3,1)(3,1)(4,1)(4,1)(5,1)(5,1)(

6、6,1)(6,1)break迷宫问题-DFS19iiiii 81234567812345679090栈栈(1,1)(1,1)(2,1)(2,1)(3,1)(3,1)(4,1)(4,1)(5,1)(5,1)(6,1)(6,1)向右方、左方均不能前进，下方路不通，上方是来路，则后退break迷宫问题-DFS20iiiii81234567 0981234567812345679090栈栈(1,1)(1,1)(2,1)(2,1)(3,1)(3,1)(4,1)(4,1)(5,1)(5,1)(5,2)(5,2)n向右方前进一步向右方前进一步break迷宫问题-DFS21iiiiii 81234567812

7、345679090n下方路不通，向右方前进一步下方路不通，向右方前进一步栈栈(1,1)(1,1)(2,1)(2,1)(3,1)(3,1)(4,1)(4,1)(5,1)(5,1)(5,3)(5,3)(5,2)(5,2)break迷宫问题-DFS22iiiiiii81234567 0981234567812345679090 向下方前进一步栈栈(1,1)(1,1)(2,1)(2,1)(3,1)(3,1)(4,1)(4,1)(5,1)(5,1)(6,1)(6,1)(5,2)(5,2)(5,3)(5,3)break迷宫问题-DFS23iiiiiii 81234567812345679090n下方路不通

8、，向右方前进一步下方路不通，向右方前进一步栈栈(1,1)(1,1)(2,1)(2,1)(3,1)(3,1)(4,1)(4,1)(5,1)(5,1)(6,4)(6,4)(5,2)(5,2)(5,3)(5,3)(6,3)(6,3)ibreak迷宫问题-DFS24iiiiiiiii 81234567812345679090n下方路不通，向右方前进一步下方路不通，向右方前进一步栈栈(1,1)(1,1)(2,1)(2,1)(3,1)(3,1)(4,1)(4,1)(5,1)(5,1)(6,5)(6,5)(5,2)(5,2)(5,3)(5,3)(6,3)(6,3)(6,4)(6,4)break迷宫问题-DF

9、S25iiiiiiiiii81234567 0981234567812345679090 向下方前进一步栈栈(1,1)(1,1)(2,1)(2,1)(3,1)(3,1)(4,1)(4,1)(5,1)(5,1)(7,5)(7,5)(5,2)(5,2)(5,3)(5,3)(6,3)(6,3)(6,4)(6,4)(6,5)(6,5)break迷宫问题-DFS26iiiiiiiiiii 81234567812345679090 向下方前进一步栈栈(1,1)(1,1)(2,1)(2,1)(3,1)(3,1)(4,1)(4,1)(5,1)(5,1)(8,5)(8,5)(5,2)(5,2)(5,3)(5,3

10、)(6,3)(6,3)(6,4)(6,4)(6,5)(6,5)(7,5)(7,5)break迷宫问题-DFSTHANK YOUSUCCESS2022-11-1428iiiiiiiiiiii 81234567812345679090n下方路不通，向右方前进一步下方路不通，向右方前进一步栈栈(1,1)(1,1)(2,1)(2,1)(3,1)(3,1)(4,1)(4,1)(5,1)(5,1)(8,6)(8,6)(5,2)(5,2)(5,3)(5,3)(6,3)(6,3)(6,4)(6,4)(6,5)(6,5)(7,5)(7,5)(8,5)(8,5)break迷宫问题-DFS29iiiiiiiiiii

11、ii 81234567812345679090n下方路不通，向右方前进一步下方路不通，向右方前进一步栈栈(1,1)(1,1)(2,1)(2,1)(3,1)(3,1)(4,1)(4,1)(5,1)(5,1)(8,7)(8,7)(5,2)(5,2)(5,3)(5,3)(6,3)(6,3)(6,4)(6,4)(6,5)(6,5)(7,5)(7,5)(8,5)(8,5)(8,6)(8,6)break迷宫问题-DFS30iiiiiiiiiiii 81234567812345679090n下方路不通，向右方前进一步，到达出口下方路不通，向右方前进一步，到达出口栈栈(1,1)(1,1)(2,1)(2,1)(

12、3,1)(3,1)(4,1)(4,1)(5,1)(5,1)(8,8)(8,8)(5,2)(5,2)(5,3)(5,3)(6,3)(6,3)(6,4)(6,4)(6,5)(6,5)(7,5)(7,5)(8,5)(8,5)(8,6)(8,6)ii(8,7)(8,7)break迷宫问题-DFS31iiiiiiiiiiiiii81234567 981234567090用栈保存了路径栈栈(1,1)(1,1)(2,1)(2,1)(3,1)(3,1)(4,1)(4,1)(5,1)(5,1)(8,8)(8,8)(5,2)(5,2)(5,3)(5,3)(6,3)(6,3)(6,4)(6,4)(6,5)(6,5)

13、(7,5)(7,5)(8,5)(8,5)(8,6)(8,6)(8,7)(8,7)迷宫问题-DFS32 入口出口 借助于队列可求得入口到出口的最短路径(若存在)81234567812345679090迷宫问题(最短路径)-BFS3311 入口出口 借助于队列可求得入口到出口的最短路径(若存在)81234567812345679090迷宫问题(最短路径)-BFS341122 入口出口 借助于队列可求得入口到出口的最短路径(若存在)81234567812345679090迷宫问题(最短路径)-BFS35112233 入口出口 借助于队列可求得入口到出口的最短路径(若存在)81234567812345

14、679090迷宫问题(最短路径)-BFS3611223434 入口出口 借助于队列可求得入口到出口的最短路径(若存在)81234567812345679090迷宫问题(最短路径)-BFS3711223453455 入口出口 借助于队列可求得入口到出口的最短路径(若存在)81234567812345679090迷宫问题(最短路径)-BFS3811262345345656 入口出口 借助于队列可求得入口到出口的最短路径(若存在)81234567812345679090迷宫问题(最短路径)-BFS3917126723453456576 入口出口 借助于队列可求得入口到出口的最短路径(若存在)8123

15、4567812345679090迷宫问题(最短路径)-BFS4017812678234534565786 入口出口 借助于队列可求得入口到出口的最短路径(若存在)81234567812345679090迷宫问题(最短路径)-BFS411789126782345345657896 入口出口 借助于队列可求得入口到出口的最短路径(若存在)812345678123456790909迷宫问题(最短路径)-BFS42178912678234510310456105789610 入口出口 借助于队列可求得入口到出口的最短路径(若存在)812345678123456790909迷宫问题(最短路径)-BFS4

16、3178912678234510 11311 10 1145610 11578961011 入口出口 借助于队列可求得入口到出口的最短路径(若存在)812345678123456790909迷宫问题(最短路径)-BFS4417891267812234510 11311 10 11 1245610 11 12578961012 11 12 入口出口 借助于队列可求得入口到出口的最短路径(若存在)812345678123456790909迷宫问题(最短路径)-BFS451789131267812234510 11311 10 11 1245610 11 12 13578961013 12 11 1

17、2 13 入口出口 借助于队列可求得入口到出口的最短路径(若存在)812345678123456790909迷宫问题(最短路径)-BFS461789131267812234510 11311 10 11 1245610 11 12 13578961013 12 11 12 13 入口出口 借助于队列可求得入口到出口的最短路径(若存在)812345678123456790909迷宫问题(最短路径)-BFS47小结DFS：使用栈保存未被检测的结点，结点按照深度优先的次序被访问并依次被压入栈中，并以相反的次序出栈进行新的检测。类似于树的先根遍历 深搜例子：走迷宫，你没有办法用分身术来站在每个走过的位

18、置。不撞南山不回头。BFS：使用队列保存未被检测的结点。结点按照宽度优先的次序被访问和进、出队列。类似于树的按层次遍历的过程 广搜例子:你的眼镜掉在地上以后，你趴在地板上找。你总是先摸最接近你的地方，如果没有，再摸远一点的地方48例题2 Oil Deposits题意：给出一个N*M的矩形区域和每个区域的状态-有/没有石油，（定义）如果两个有石油的区域是相邻的（水平、垂直、斜）则认为这是属于同一个oil pocket。求这块矩形区域一共有多少oil pocket。49 思路：对于每个有油区域，找出所有与它同属一个oil pocket的有油区域，最后计算一共有多少个oil pocket。？怎样去找

19、出所有与它同属一个oil pocketBFS：找到一个起点；从这个点出发，枚举四周寻找有油区域；顺序从找到的新的区域出发，循环上述过程，直到没有新的区域加入。？怎样去标志同属一个oil pocket的有油区域设置一个访问标志代表此区域有没有被包含过，这样的话调用BFS的次数就=oil pocket的数目。当然DFS也是可以这样做的。FloodFill50框架：Void BFS(int i,int j)初始化队列Q；while(Q不为空）取出队首元素u;枚举元素u的相邻区域，if(此区域有油)入队;访问标记;Int main()枚举所有区域，if(此区域有油&没有被访问过)BFS(,)51练习http:/:8080/judge/contest/view.action?cid=17535#overview密码：12345652推荐书籍THANK YOUSUCCESS2022-11-14