资源描述：
《ACM算法设计-BFS(广度搜索)-DFS入门(深度搜索)详解》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、ACM算法设计 BFS(广度搜索)-DFS(深度搜索) 详解BFS算法byplato复习DFS算法思想：一直往深处走，直到找到解或者走不下去为止框架：DFS(dep,…)//dep代表目前DFS的深度{if(找到解
2、
3、走不下去了){…return;}枚举下一种情况，DFS(dep+1,…)}3DFS的遍历方式HALIFBCDEJGKS4存在其他的遍历方式？5BFS的思想1.从初始状态S开始，利用规则，生成下一层的状态。2.顺序检查下一层的所有状态，看是否出现目标状态G。否则就对该层所有状态节点，分别利
4、用规则。生成再下一层的所有状态节点。3.继续按上面思想生成再下一层的所有状态节点，这样一层一层往下展开。直到出现目标状态为止。按层次的顺序来遍历搜索树6BFS框架通常用队列(先进先出,FIFO)实现初始化队列Q.Q={起点s};标记s为己访问;while(Q非空){取Q队首元素u;u出队;if(u==目标状态){…}所有与u相邻且未被访问的点进入队列;标记u为已访问;}78123456781234567入口出口寻找一条从入口到出口的通路迷宫问题8东南北(上)西(左)前进方向：上(北)、下(南)、左(西
5、)、右(东)首先从下方开始，按照逆时针方向搜索下一步可能前进的位置迷宫问题-DFS9入口出口在迷宫周围加墙，避免判断是否出界81234567812345679090迷宫问题-DFS1081234567812345679090在寻找出口的过程中，每前进一步，当前位置入栈；每回退一步，栈顶元素出栈栈(1,1)迷宫问题-DFS11i81234567812345679090栈(1,1)(2,1)向下方前进一步迷宫问题-DFS12i81234567812345679090栈(1,1)(2,1)i(3,1)向下方
6、前进一步迷宫问题-DFS13ii81234567812345679090栈(1,1)(2,1)(4,1)(3,1)i向下方前进一步break迷宫问题-DFS14iiii81234567812345679090栈(1,1)(2,1)(5,1)(3,1)(4,1)向下方前进一步break迷宫问题-DFS15iiiii81234567812345679090栈(1,1)(2,1)(6,1)(3,1)(4,1)(5,1)向下方前进一步break迷宫问题-DFS16iiiiii迷宫问题(续)8123456781
7、2345679090栈(1,1)(2,1)(7,1)(3,1)(4,1)(5,1)(6,1)向下方前进一步break17iiiiii@81234567812345679090向下方、右方、左方均不能前进，上方是来路，则后退栈(1,1)(2,1)(7,1)(3,1)(4,1)(5,1)(6,1)break迷宫问题-DFS18iiiii@@81234567812345679090栈(1,1)(2,1)(3,1)(4,1)(5,1)(6,1)向右方、左方均不能前进，下方路不通，上方是来路，则后退break迷
8、宫问题-DFS19iiiii@@812345670981234567812345679090栈(1,1)(2,1)(3,1)(4,1)(5,1)(5,2)向右方前进一步break迷宫问题-DFS20iiiiii@@81234567812345679090下方路不通，向右方前进一步栈(1,1)(2,1)(3,1)(4,1)(5,1)(5,3)(5,2)break迷宫问题-DFS21iiiiiii@@812345670981234567812345679090向下方前进一步栈(1,1)(2,1)(3,1)
9、(4,1)(5,1)(6,1)(5,2)(5,3)break迷宫问题-DFS22iiiiiii@@81234567812345679090下方路不通，向右方前进一步栈(1,1)(2,1)(3,1)(4,1)(5,1)(6,4)(5,2)(5,3)(6,3)ibreak迷宫问题-DFS23iiiiiii@ii@81234567812345679090下方路不通，向右方前进一步栈(1,1)(2,1)(3,1)(4,1)(5,1)(6,5)(5,2)(5,3)(6,3)(6,4)break迷宫问题-DFS2
10、4iiiiiii@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迷宫问题-DFS25iiiiiii@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迷宫
