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

1、ACM算法设计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首先从下方开始，按照逆时针方向搜索下一步首先从下方开始，按照逆时针方向搜索下一步可能前进的位置可能前进的位置迷宫问题-DFS10入口出口 在迷宫周围加墙

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

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

5、,1)(3,1)(4,1)(4,1)(5,1)(5,1)(6,1)(6,1) 向下方前进一步18iiiiii 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)迷宫问题-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)向右方、左方均不能前进，下方路不通，上方是来路，则后退迷宫问

6、题-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向右方前进一步向右方前进一步迷宫问题-DFS21iiiiii 81234567812345679090n下方路不通，向右方前进一步下方路不通，向右方前进一步栈栈(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)迷宫问题-DFS22iiiiiii81234567 098123456781234567

7、9090 向下方前进一步栈栈(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)迷宫问题-DFS23iiiiiii 81234567812345679090n下方路不通，向右方前进一步下方路不通，向右方前进一步栈栈(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)i迷宫问题-DFS24iiiiiiiii 81234567812345679090n下方路不通，向

8、右方前进一步下方路不通，向右方前进一步栈栈(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)迷宫问题-DFS25iiiiiiiiii81234567 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)迷宫问题-DFS

9、26iiiiiiiiiii 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)(6,3)(6,3)(6,4)(6,4)(6,5)(6,5)(7,5)(7,5)迷宫问题-DFS27iiiiiiiiiiii 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

10、)(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)迷宫问题-DFS28iiiiiiiiiiiii 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)迷宫问题-DFS29iiiiiiiiiii

11、i 81234567812345679090n下方路不通，向右方前进一步，到达出口下方路不通，向右方前进一步，到达出口栈栈(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)(7,5)(7,5)(8,5)(8,5)(8,6)(8,6)ii(8,7)(8,7)迷宫问题-DFS30iiiiiiiiiiiiii81234567 981234567090用栈保存了路径栈栈(1,1)(1,1)(2,1)(2,1)(3,1)(3,1)(4,

12、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)(8,7)(8,7)迷宫问题-DFS31 入口出口 借助于队列可求得入口到出口的最短路径(若存在)81234567812345679090迷宫问题(最短路径)-BFS3211 入口出口 借助于队列可求得入口到出口的最短路径(若存在)81234567812345679090迷宫问题(最短路径)-BFS331122 入口出口 借助于队列可求得入口到出口的最短路径(若存在)81234567

13、812345679090迷宫问题(最短路径)-BFS34112233 入口出口 借助于队列可求得入口到出口的最短路径(若存在)81234567812345679090迷宫问题(最短路径)-BFS3511223434 入口出口 借助于队列可求得入口到出口的最短路径(若存在)81234567812345679090迷宫问题(最短路径)-BFS3611223453455 入口出口 借助于队列可求得入口到出口的最短路径(若存在)81234567812345679090迷宫问题(最短路径)-BFS3711262345345656 入口出口 借助于队列可求得入口到出口的最短路径(若存在)812345678

14、12345679090迷宫问题(最短路径)-BFS3817126723453456576 入口出口 借助于队列可求得入口到出口的最短路径(若存在)81234567812345679090迷宫问题(最短路径)-BFS3917812678234534565786 入口出口 借助于队列可求得入口到出口的最短路径(若存在)81234567812345679090迷宫问题(最短路径)-BFS401789126782345345657896 入口出口 借助于队列可求得入口到出口的最短路径(若存在)812345678123456790909迷宫问题(最短路径)-BFS41178912678234510310

15、456105789610 入口出口 借助于队列可求得入口到出口的最短路径(若存在)812345678123456790909迷宫问题(最短路径)-BFS42178912678234510 11311 10 1145610 11578961011 入口出口 借助于队列可求得入口到出口的最短路径(若存在)812345678123456790909迷宫问题(最短路径)-BFS4317891267812234510 11311 10 11 1245610 11 12578961012 11 12 入口出口 借助于队列可求得入口到出口的最短路径(若存在)812345678123456790909迷宫问题

16、(最短路径)-BFS441789131267812234510 11311 10 11 1245610 11 1212 11 12 13 入口出口 借助于队列可求得入口到出口的最短路径(若存在)812345678123456790909迷宫问题(最短路径)-BFS451789131267812234510 11311 10 11 1245610 11 1212 11 12 13 入口出口 借助于队列可求得入口到出口的最短路径(若存在)812345678123456790909迷宫问题(最短路径)-BFS46小结DFS：使用栈保存未被检测的结点

17、，结点按照深度优先的次序被访问并依次被压入栈中，并以相反的次序出栈进行新的检测。 类似于树的先根遍历 深搜例子：走迷宫，你没有办法用分身术来站在每个走过的位置。不撞南山不回头。BFS：使用队列保存未被检测的结点。结点按照宽度优先的次序被访问和进、出队列。 类似于树的按层次遍历的过程 广搜例子:你的眼镜掉在地上以后，你趴在地板上找。你总是先摸最接近你的地方，如果没有，再摸远一点的地方47例题2 Oil Deposits题意：给出一个N*M的矩形区域和每个区域的状态 - 有/没有石油，（定义）如果两个有石油的区域是相邻的（水平、垂直、斜）则认为这是属于同一个oil pocket。求这块矩形区域一共有多少oil pocket 。48 思路：对于每个有油区域，找出所有与它同属一个oil pocket的有油区域，最后计算一共有多少个oil pocket。？怎样去找出所有与它同属一个oil pocketBFS：找到一个起点；从这个点出发，枚举四周寻找有油区域；顺序从找到的新的区域出发，循环上述过程，直到没有新的区域加入。？怎样去标志同属一个oil pocket的有油