广度优先搜索

广度优先搜索讲师:目录A二三一理解什么是广度优先搜索掌握队列在算法地基本应用掌握广度优先搜索算法地步骤理解常见问题如艰难旅行问题,混乱地铁问题,与温室大棚问题四什么是广度搜索与上一章深度优先遍历相似,广度优先遍历也是一个解决图问题地遍历算法。但不同于深度优先遍历,广度优先遍历总是先去查询距离初始状态最近地状态,而不是一直向最"深"处查询结果。广度优先搜索广度优先搜索广度优先遍历算法与深度优先遍历算法具有一定相通地质,例如广度优先遍历算法也可以解决走迷宫问题。但如果使用广度优先遍历思想地走迷宫,因为其搜索地条件发生了改变,搜索地宗旨就不在于最快地有逻辑地走出迷宫,而在于寻遍迷宫地每一个角落。深度优先搜索走迷宫广度优先搜索走迷宫队列A队列队列这种数据结构是广度优先遍历算法优先选择地数据结构一,因为队列地存储机制为先先出,而广度优先遍历算法恰好需要保证优先访问已访问顶点地未访问邻接点。因此队列最适合广度优先算法地存储法则。二,队列这个数据结构只支持两个基本操作:将新元素从队尾加入队列,与将队首元素移出队列。相比于其它数据结构如数组等,队列因为操作简单因此效率高。经典例题讲解A艰难旅行问题现已知一个大小为𝑛×𝑚格地地图,地图只有可能出现两个数字:零或一,现规定如果位于数字为零地格子上,下一步只能往相邻四个格子数字为一地格子走,如果位于数字为一地格子上,则下一步只能往相邻四个格子数字为零地格子走。如果给定妳地起点格子,且只能向上下左右四个方向移动,求妳能在这个𝑛×𝑚地格地图到达多少格子(包含自身)？问题描述:艰难旅行问题如上二图例子所示,假设地图为一个五×五地方格图,且给定地起点为左上角灰色地方格。那么如果地图上地零,一分布如上图一所示,则从灰色格子出发,可以从一,到达右边与下方地零,再到达右边与下方地一,从而到达地图上地所有方格。因此图一求解出地答案应为二五,即可以到达图上地所有方格。而如果地图上地零,一分布如上图二所示,仍从左上角灰色地格子出发,我们会发现其右边与下方地方格均为一,因此无法移动到任何其它方格,求解出能到达地格子数为一。艰难旅行问题假设一个地图如左下图（外围地数字为行列标号）,并且起点为第三行第三列地灰色格子。我们可以创建一个队列结构,并将起点加入队列,完成初始化（队列地格子均用行列标号表示,如第一行第二列地方格表示为(一,二)）。队列地状态如右下所示。广度遍历策略:艰难旅行问题此时判断现所位于方格地四周方格是否可以到达。(三,三)位置地方格地数字为零,其上下左右地四个方格地数字均为一,因此其上下左右地方格均能到达。此时将方格(三,三)移出队列,并将(三,四)(三,二)(二,三)(四,三)加入队列。广度遍历策略:艰难旅行问题这时我们只需重复之前地步骤,将队列最前面地方格移出队列,并将从该方格出发可以到达地四周方格加入队列即可。如果即将加入队列地方格已经被加入过,则跳过不再加入队列,避免重复遍历。广度遍历策略:………………艰难旅行问题根据上述操作规则如此反复,直到队列为空为止,即可求得本题地答案。最终结果如下图所示,所有灰色地方格均可以从起始点(三,三)到达,一可以到达一一个方格。广度遍历策略:混乱地铁问题A混乱地铁问题在某一个城市地铁网极度混乱。一条地铁线路上有n个地铁站,分别编号为一到n。地铁线路上地每一个站都会停靠地铁,每一个地铁站上都有一个数字m,代表从此站出发乘客需要乘坐地站数。每个地铁站都有通往两个方向地地铁。因此既可以向编号大地方向前m站,也可以向编号小地方向前m站。但如果前后超出了地铁站地范围,则该地铁不可被乘坐。例如编号为一地地铁上地数字为三,那么在该地铁站上车,可以向正方向坐车到四号地铁站。但不能反方向坐车到-二号地铁站,因为-二号地铁站不存在。现在乘客从A号地铁站出发,想要到达B号地铁站,求它能否到达,最少要搭乘多少次地铁？问题描述:混乱地铁问题如图下所示,如果一有五个地铁站,其编号依次为一,二,三,四,五。而每个地铁站地数字分别为二,四,一,二,三情况举例:混乱地铁问题如果乘客从一号地铁站出发,而它目地地是二号地铁站,则它有两个选择,向正方向坐车,或向反方向坐车。一号车站地数字为二,因此可以到达三号地铁站与-一号地铁站。又因为-一号地铁站并不存在,所以从一号地铁站出发只能到达三号地铁站。综上我们可以得出结论:从一号地铁站出发,到达三号地铁站最少要坐一趟地铁,如图下所示。同时想象有一个队列,其记录着现在所在地地铁站号码,而每次加入队列地是可以到达地地铁站号码。情况举例:混乱地铁问题此时到达三号地铁站。三号地铁站地数字为一,因此可以向正方向坐一站车到达四号地铁站,也可以向反方向坐一站车直接到达目地地二号地铁站。同样我们也可以得出结论:从一号地铁站出发,到达二号地铁站与四号地铁站至少需要坐两趟地铁,如图下所示。情况举例:混乱地铁问题此时已经到达目地地。但值得注意地是,当我们从四号地铁站出发时,如果向正方向乘坐二站地铁（四号地铁站上地数字为二）,将超出地铁站范围,因此无法向正方向乘坐地铁。如果向反方向乘坐二站地铁,也将会到达目地地二号地铁站。如下图所示情况举例:但如果仔细思考使用队列数据结构地广度优先搜索算法,不难推导出最优地方案一定比次优地方案先入队列,因为广度优先搜索算法具有层次,每一次遍历距离最近或距离相同地目地。混乱地铁问题以上述实例地步骤行广度优先搜索,便能求解出最佳答案温室大棚问题A温室大棚问题在一个温室大棚种有西红柿。该温室大棚使用种植架来种植西红柿,并使用造光来照射西红柿。在种植架上地西红柿果实以二叉树地结构排列,二叉树地节点代表西红柿,二叉树地链接代表茎。不幸地是,温室大棚两侧地照射灯只有右侧地工作,而左侧地灯因某些原因无法使用。种植员在准备收获西红柿时才发现这些问题。检查后发现,因为光地接受度不够,只有每一层种植架上最右侧地西红柿正常成熟,可以食用。现给出种植架上西红柿地二叉树结构,求如果在上述情况下,有多少西红柿是成熟地。问题描述:温室大棚问题这道题我们可以用广度优先搜索算法来处理树结构地图,例如下两图即为问题描述地两个例子（阴影部分代表成熟）至此,我们可以用更简洁地语言来诠释本题地核心:寻找二叉树每一层最右侧地节点。温室大棚问题解题思路:

我们需要对二叉树行分层,因为只有分层之后才能准确地对每一层地节点行遍历,寻找到最右边地节点,如下图所示。温室大棚问题解题思路:我们只需要将一整层放入队列,寻找到最右边地节点,再通过队列地节点更新下一层地节点,将所有下一层地节点放入队列,并把前一层地节点移出队列,直到没有节点可以加入队列,队列为空为止。例如我们可以先将第一层地有且仅有地根节点（一号节点）放入队列,判定其为最右边地节点后,将其地全部子节