《ACM算法设计-BFS(广度搜索)-DFS入门(深度搜索)详解课件》由会员分享，可在线阅读，更多相关《ACM算法设计-BFS(广度搜索)-DFS入门(深度搜索)详解课件（51页珍藏版）》请在金锄头文库上搜索。
1、ACM算法设计BFS(广度搜索)-DFS(深度搜索)详解ACM算法设计-BFS(广度搜索)-DFS入门(深度搜索)详解BFS算法 by platoACM算法设计-BFS(广度搜索)-DFS入门(深度搜索)详解复习复习DFS算法算法思想： 一直往深处走，直到找到解或者走不下去为止框架：DFS(dep,) /dep代表目前DFS的深度 if (找到解|走不下去了) return; 枚举下一种情况，DFS(dep+1,)3ACM算法设计-BFS(广度搜索)-DFS入门(深度搜索)详解DFS的遍历方式HALIFBCDEJGKS4ACM算法设计-BFS(广度搜索)-DFS入门(深度搜索)详解存在其他的遍
2、历方式？5ACM算法设计-BFS(广度搜索)-DFS入门(深度搜索)详解BFS的思想1.从初始状态S开始，利用规则，生成下一层的状态。2.顺序检查下一层的所有状态，看是否出现目标状态G。否则就对该层所有状态节点，分别利用规则。生成再下一层的所有状 态节点。3.继续按上面思想生成再下一层的所有状态节点，这样一层一层往下展开。直到出现目标状态为止。按层次的顺序来遍历搜索树6ACM算法设计-BFS(广度搜索)-DFS入门(深度搜索)详解BFS框架通常用队列(先进先出,FIFO)实现初始化队列Q.Q=起点s; 标记s为己访问;while (Q非空) 取Q队首元素u; u出队;if (u = 目标状态)
3、 所有与u相邻且未被访问的点进入队列;标记u为已访问;7ACM算法设计-BFS(广度搜索)-DFS入门(深度搜索)详解8123456781234567入口入口出口出口寻找一条从入口到出口的通路迷宫问题8ACM算法设计-BFS(广度搜索)-DFS入门(深度搜索)详解东南北(上上)西(左左)前进方向：上(北)、下(南)、左(西)、右(东)n首先从下方开始，按照逆时针方向搜索下一步首先从下方开始，按照逆时针方向搜索下一步可能前进的位置可能前进的位置迷宫问题-DFS9ACM算法设计-BFS(广度搜索)-DFS入门(深度搜索)详解入口出口在迷宫周围加墙，避免判断是否出界81234567812345679
4、090迷宫问题-DFS10ACM算法设计-BFS(广度搜索)-DFS入门(深度搜索)详解81234567812345679090在寻找出口的过程中，每前进一步，当前位置入栈；每回退一步，栈顶元素出栈栈栈(1,1)(1,1)迷宫问题-DFS11ACM算法设计-BFS(广度搜索)-DFS入门(深度搜索)详解i81234567812345679090栈栈(1,1)(1,1)(2,1)(2,1)向下方前进一步迷宫问题-DFS12ACM算法设计-BFS(广度搜索)-DFS入门(深度搜索)详解i81234567812345679090栈栈(1,1)(1,1)(2,1)(2,1)i(3,1)(3,1)向下方
5、前进一步迷宫问题-DFS13ACM算法设计-BFS(广度搜索)-DFS入门(深度搜索)详解ii81234567812345679090栈栈(1,1)(1,1)(2,1)(2,1)(4,1)(4,1)(3,1)(3,1)i向下方前进一步break迷宫问题-DFS14ACM算法设计-BFS(广度搜索)-DFS入门(深度搜索)详解iiii81234567812345679090栈栈(1,1)(1,1)(2,1)(2,1)(5,1)(5,1)(3,1)(3,1)(4,1)(4,1)向下方前进一步break迷宫问题-DFS15ACM算法设计-BFS(广度搜索)-DFS入门(深度搜索)详解iiiii 81
6、234567812345679090栈栈(1,1)(1,1)(2,1)(2,1)(6,1)(6,1)(3,1)(3,1)(4,1)(4,1)(5,1)(5,1)向下方前进一步break迷宫问题-DFS16ACM算法设计-BFS(广度搜索)-DFS入门(深度搜索)详解iiiiii迷宫问题(续)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)向下方前进一步break17ACM算法设计-BFS(广度搜索)-DFS入门(深度搜索)详解iiiiii 8123456781
7、2345679090向下方 、右方、左方均不能前进，上方是来路，则后退栈栈(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)break迷宫问题-DFS18ACM算法设计-BFS(广度搜索)-DFS入门(深度搜索)详解iiiii 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迷宫问题-DFS19ACM算法设计-BFS(广度搜索)
8、-DFS入门(深度搜索)详解iiiii81234567 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迷宫问题-DFS20ACM算法设计-BFS(广度搜索)-DFS入门(深度搜索)详解iiiiii 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)b
9、reak迷宫问题-DFS21ACM算法设计-BFS(广度搜索)-DFS入门(深度搜索)详解iiiiiii81234567 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迷宫问题-DFS22ACM算法设计-BFS(广度搜索)-DFS入门(深度搜索)详解iiiiiii 81234567812345679090n下方路不通，向右方前进一步下方路不通，向右方前进一步栈栈(1,1)(1,1)(2,1)(2,1)(3,1)
10、(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迷宫问题-DFS23ACM算法设计-BFS(广度搜索)-DFS入门(深度搜索)详解iiiiiiiii 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迷宫问题-DFS24ACM算法设计-BFS(广度
11、搜索)-DFS入门(深度搜索)详解iiiiiiiiii81234567 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迷宫问题-DFS25ACM算法设计-BFS(广度搜索)-DFS入门(深度搜索)详解iiiiiiiiiii 81234567812345679090向下方前进一步栈栈(1,1)(1,1)(2,1)(2,1)(3,1)(3,1)(4,1)(
12、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)break迷宫问题-DFS26ACM算法设计-BFS(广度搜索)-DFS入门(深度搜索)详解iiiiiiiiiiii 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,
13、5)(7,5)(7,5)(8,5)(8,5)break迷宫问题-DFS27ACM算法设计-BFS(广度搜索)-DFS入门(深度搜索)详解iiiiiiiiiiiii 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迷宫问题-DFS28ACM算法设计-BFS(广度
14、搜索)-DFS入门(深度搜索)详解iiiiiiiiiiii 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)break迷宫问题-DFS29ACM算法设计-BFS(广度搜索)-DFS入门(深度搜索)详解iiiiiiiiiiiii
15、i81234567 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)(7,5)(7,5)(8,5)(8,5)(8,6)(8,6)(8,7)(8,7)迷宫问题-DFS30ACM算法设计-BFS(广度搜索)-DFS入门(深度搜索)详解 入口出口借助于队列可求得入口到出口的最短路径(若存在)81234567812345679090迷宫问题(最短路径)-BFS31ACM算法设计-BFS(广度
16、搜索)-DFS入门(深度搜索)详解11 入口出口借助于队列可求得入口到出口的最短路径(若存在)81234567812345679090迷宫问题(最短路径)-BFS32ACM算法设计-BFS(广度搜索)-DFS入门(深度搜索)详解1122 入口出口借助于队列可求得入口到出口的最短路径(若存在)81234567812345679090迷宫问题(最短路径)-BFS33ACM算法设计-BFS(广度搜索)-DFS入门(深度搜索)详解112233 入口出口借助于队列可求得入口到出口的最短路径(若存在)81234567812345679090迷宫问题(最短路径)-BFS34ACM算法设计-BFS(广度搜索)
17、-DFS入门(深度搜索)详解11223434 入口出口借助于队列可求得入口到出口的最短路径(若存在)81234567812345679090迷宫问题(最短路径)-BFS35ACM算法设计-BFS(广度搜索)-DFS入门(深度搜索)详解11223453455 入口出口借助于队列可求得入口到出口的最短路径(若存在)81234567812345679090迷宫问题(最短路径)-BFS36ACM算法设计-BFS(广度搜索)-DFS入门(深度搜索)详解11262345345656 入口出口借助于队列可求得入口到出口的最短路径(若存在)81234567812345679090迷宫问题(最短路径)-BFS3
18、7ACM算法设计-BFS(广度搜索)-DFS入门(深度搜索)详解17126723453456576 入口出口借助于队列可求得入口到出口的最短路径(若存在)81234567812345679090迷宫问题(最短路径)-BFS38ACM算法设计-BFS(广度搜索)-DFS入门(深度搜索)详解17812678234534565786 入口出口借助于队列可求得入口到出口的最短路径(若存在)81234567812345679090迷宫问题(最短路径)-BFS39ACM算法设计-BFS(广度搜索)-DFS入门(深度搜索)详解1789126782345345657896 入口出口借助于队列可求得入口到出口的
19、最短路径(若存在)812345678123456790909迷宫问题(最短路径)-BFS40ACM算法设计-BFS(广度搜索)-DFS入门(深度搜索)详解178912678234510310456105789610 入口出口借助于队列可求得入口到出口的最短路径(若存在)812345678123456790909迷宫问题(最短路径)-BFS41ACM算法设计-BFS(广度搜索)-DFS入门(深度搜索)详解178912678234510 11311 10 1145610 11578961011 入口出口借助于队列可求得入口到出口的最短路径(若存在)812345678123456790909迷宫问题
20、(最短路径)-BFS42ACM算法设计-BFS(广度搜索)-DFS入门(深度搜索)详解17891267812234510 11311 10 11 1245610 11 12578961012 11 12 入口出口借助于队列可求得入口到出口的最短路径(若存在)812345678123456790909迷宫问题(最短路径)-BFS43ACM算法设计-BFS(广度搜索)-DFS入门(深度搜索)详解1789131267812234510 11311 10 11 1245610 11 12 13578961013 12 11 12 13 入口出口借助于队列可求得入口到出口的最短路径(若存在)812345
21、678123456790909迷宫问题(最短路径)-BFS44ACM算法设计-BFS(广度搜索)-DFS入门(深度搜索)详解1789131267812234510 11311 10 11 1245610 11 12 13578961013 12 11 12 13 入口出口借助于队列可求得入口到出口的最短路径(若存在)812345678123456790909迷宫问题(最短路径)-BFS45ACM算法设计-BFS(广度搜索)-DFS入门(深度搜索)详解小结DFS：使用栈保存未被检测的结点，结点按照深度优先的次序被访问并依次被压入栈中，并以相反的次序出栈进行新的检测。 类似于树的先根遍历深搜例子：
22、走迷宫，你没有办法用分身术来站在每个走过的位置。不撞南山不回头。BFS：使用队列保存未被检测的结点。结点按照宽度优先的次序被访问和进、出队列。类似于树的按层次遍历的过程广搜例子:你的眼镜掉在地上以后，你趴在地板上找。你总是先摸最接近你的地方，如果没有，再摸远一点的地方46ACM算法设计-BFS(广度搜索)-DFS入门(深度搜索)详解例题2 Oil Deposits题意：给出一个N*M的矩形区域和每个区域的状态 - 有/没有石油，（定义）如果两个有石油的区域是相邻的（水平、垂直、斜）则认为这是属于同一个oil pocket。求这块矩形区域一共有多少oil pocket 。47ACM算法设计-BF
23、S(广度搜索)-DFS入门(深度搜索)详解 思路：对于每个有油区域，找出所有与它同属一个oil pocket的有油区域，最后计算一共有多少个oil pocket。？怎样去找出所有与它同属一个oil pocketBFS：找到一个起点；从这个点出发，枚举四周寻找有油区域；顺序从找到的新的区域出发，循环上述过程，直到没有新的区域加入。？怎样去标志同属一个oil pocket的有油区域设置一个访问标志代表此区域有没有被包含过，这样的话调用BFS的次数就= oil pocket的数目。当然DFS也是可以这样做的。 FloodFill48ACM算法设计-BFS(广度搜索)-DFS入门(深度搜索)详解框架：Void BFS(int i,int j)初始化队列Q；while(Q不为空）取出队首元素u;枚举元素u的相邻区域， if (此区域有油)入队;访问标记;Int main()枚举所有区域，if (此区域有油&没有被访问过)BFS(,)49ACM算法设计-BFS(广度搜索)-DFS入门(深度搜索)详解练习密码 ：12345650ACM算法设计-BFS(广度搜索)-DFS入门(深度搜索)详解推荐书籍51ACM算法设计-BFS(广度搜索)-DFS入门(深度搜索)详解
