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

2020/4/17ACM算法设计BFS(广度搜索)-DFS(深度搜索)详解BFS算法byplato3复习DFS算法思想：一直往深处走，直到找到解或者走不下去为止框架：DFS(dep,…)//dep代表目前DFS的深度{if(找到解||走不下去了){…return;}枚举下一种情况，DFS(dep+1,…)}4DFS的遍历方式HALIFBCDEJGKS5存在其他的遍历方式？6BFS的思想1.从初始状态S开始，利用规则，生成下一层的状态。2.顺序检查下一层的所有状态，看是否出现目标状态G。否则就对该层所有状态节点，分别利用规则。生成再下一层的所有状态节点。3.继续按上面思想生成再下一层的所有状态节点，这样一层一层往下展开。直到出现目标状态为止。按层次的顺序来遍历搜索树7BFS框架通常用队列(先进先出,FIFO)实现初始化队列Q.Q={起点s};标记s为己访问;while(Q非空){取Q队首元素u;u出队;if(u==目标状态){…}所有与u相邻且未被访问的点进入队列;标记u为已访问;}88123456781234567入口出口•寻找一条从入口到出口的通路迷宫问题9东南北(上)西(左)•前进方向：上(北)、下(南)、左(西)、右(东)首先从下方开始，按照逆时针方向搜索下一步可能前进的位置迷宫问题-DFS10入口出口•在迷宫周围加墙，避免判断是否出界81234567812345679090迷宫问题-DFS1181234567812345679090•在寻找出口的过程中，每前进一步，当前位置入栈；每回退一步，栈顶元素出栈栈(1,1)迷宫问题-DFS12i81234567812345679090栈(1,1)(2,1)•向下方前进一步迷宫问题-DFS13i81234567812345679090栈(1,1)(2,1)i(3,1)•向下方前进一步迷宫问题-DFS14ii81234567812345679090栈(1,1)(2,1)(4,1)(3,1)i•向下方前进一步break迷宫问题-DFS15iiii81234567812345679090栈(1,1)(2,1)(5,1)(3,1)(4,1)•向下方前进一步break迷宫问题-DFS16iiiii81234567812345679090栈(1,1)(2,1)(6,1)(3,1)(4,1)(5,1)•向下方前进一步break迷宫问题-DFS17iiiiii迷宫问题(续)81234567812345679090栈(1,1)(2,1)(7,1)(3,1)(4,1)(5,1)(6,1)•向下方前进一步break18iiiiii@81234567812345679090•向下方、右方、左方均不能前进，上方是来路，则后退栈(1,1)(2,1)(7,1)(3,1)(4,1)(5,1)(6,1)break迷宫问题-DFS19iiiii@@81234567812345679090栈(1,1)(2,1)(3,1)(4,1)(5,1)(6,1)•向右方、左方均不能前进，下方路不通，上方是来路，则后退break迷宫问题-DFS20iiiii@@812345670981234567812345679090栈(1,1)(2,1)(3,1)(4,1)(5,1)(5,2)向右方前进一步break迷宫问题-DFS21iiiiii@@81234567812345679090下方路不通，向右方前进一步栈(1,1)(2,1)(3,1)(4,1)(5,1)(5,3)(5,2)break迷宫问题-DFS22iiiiiii@@812345670981234567812345679090•向下方前进一步栈(1,1)(2,1)(3,1)(4,1)(5,1)(6,1)(5,2)(5,3)break迷宫问题-DFS23iiiiiii@@81234567812345679090下方路不通，向右方前进一步栈(1,1)(2,1)(3,1)(4,1)(5,1)(6,4)(5,2)(5,3)(6,3)ibreak迷宫问题-DFS24iiiiiii@ii@81234567812345679090下方路不通，向右方前进一步栈(1,1)(2,1)(3,1)(4,1)(5,1)(6,5)(5,2)(5,3)(6,3)(6,4)break迷宫问题-DFS25iiiiiii@iii@812345670981234567812345679090•向下方前进一步栈(1,1)(2,1)(3,1)(4,1)(5,1)(7,5)(5,2)(5,3)(6,3)(6,4)(6,5)break迷宫问题-DFS26iiiiiii@iii@i81234567812345679090•向下方前进一步栈(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迷宫问题-DFS27iiiiiii@iii@ii81234567812345679090下方路不通，向右方前进一步栈(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迷宫问题-DFS28iiiiiii@iii@iii81234567812345679090下方路不通，向右方前进一步栈(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迷宫问题-DFS29iiiiiii@iii@ii81234567812345679090下方路不通，向右方前进一步，到达出口栈(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)ii(8,7)break迷宫问题-DFS30iiiiiii@iii@iiii81234567981234567090用栈保存了路径栈(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)迷宫问题-DFS31入口出口•借助于队列可求得入口到出口的最短路径(若存在)81234567812345679090迷宫问题(最短路径)-BFS3211入口出口•借助于队列可求得入口到出口的最短路径(若存在)81234567812345679090迷宫问题(最短路径)-BFS331122入口出口•借助于队列可求得入口到出口的最短路径(若存在)81234567812345679090迷宫问题(最短路径)-BFS34112233入口出口•借助于队列可求得入口到出口的最短路径(若存在)81234567812345679090迷宫问题(最短路径)-BFS3511223434入口出口•借助于队列可求得入口到出口的最短路径(若存在)81234567812345679090迷宫问题(最短路径)-BFS3611223453455入口出口•借助于队列可求得入口到出口的最短路径(若存在)81234567812345679090迷宫问题(最短路径)-BFS3711262345345656入口出口•借助于队列可求得入口到出口的最短路径(若存在)81234567812345679090迷宫问题(最短路径)-BFS3817126723453456576入口出口•借助于队列可求得入口到出口的最短路径(若存在)81234567812345679090迷宫问题(最短路径)-BFS3917812678234534565786入口出口•借助于队列可求得入口到出口的最短路径(若存在)81234567812345679090迷宫问题(最短路径)-BFS401789126782345345657896入口出口•借助于队列可求得入口到出口的最短路径(若存在)812345678123456790909迷宫问题(最短路径)-BFS41178912678234510310456105789610入口出口•借助于队列可求得入口到出口的最短路径(若存在)812345678123456790909迷宫问题(最短路径)-BFS421789126782345101131110114561011578961011入口出口•借助于队列可求得入口到出口的最短路径(若存在)812345678123456790909迷宫问题(最短路径)-BFS4317891267812234510113111011124561011125789610121112入口出口•借助于队列可求得入口到出口的最短路径(若存在)812345678123456790909迷宫问题(最短路径)-BFS441789131267812234510113111011124561011121357896101312111213入口出口•借助于队列可求得入口到出口的最短路径(若存在)812345678123456790909迷宫问题(最短路径)-BFS451789131267812234510113111011124561011121357896101312111213入口出口•借助于队列可求得入口到出口的最短路径(若存在)812345678123456790909迷宫问题(最短路径)-BFS46小结DFS：使用栈保存未被检测的结点，结点按照深度优先的次序被访问并依次被压入栈中，并以相反的次序出栈进行新的检测。–类似于树的先根遍历–深搜例子：走迷宫，你没有办法用分身术来站在每个走过的位置。不撞南山不回头。BFS：使用队列保存未被检测的结点。结点按照宽度优先的次序被访问和进、出队列。–类似于树的按层次遍历的过程–广搜例子:你的眼镜掉在地上以后，你趴在地板上找。你总是先摸最接近你的地方，如果没有，再摸远一点的地方……47例题2–OilDeposits题意：给出一个N*M的矩形区域和每个区域的状态--有/没有石油，（定义）如果两个有石油的区域是相邻的（水平、垂直、斜）则认为这是属于同一个oilpocket。求这块矩形区域一共有多少oilpocket。48思路：对于每个有油区域，找出所有与它同属一个oilpocket的有油区域，最后计算一共有多少个oilpocket。？怎样去找出所有与它同属一个oilpocketBFS：找到一个起点；从这个点出发，枚举四周寻找有油区域；顺序从找到的新的区域出发，循环上述过程，直到没有新的区域加入。？怎样去标志同属一个oilpocket的有油区域设置一个访问标志代表此区域有没有被包含过，这样的话调用BFS的次数就=oilpocket的数目。当然DFS也是可以这样做的。FloodFill49框架：VoidBFS(inti,intj){初始化队列Q；while(Q不为空）{取出队首元素u;枚举元素u的相邻区域，if(此区域有油){入队;访问标记;}}}Intmain(){…枚举所有区域，if(此区域有油&&没有被访问过)BFS(…,…)}50练习=17535#overview密码：12345651推荐书籍