广度优先搜索-课件

1、广度优先搜索（BFS）赵和旭广度优先搜索（BFS）赵和旭广度优先搜索广度优先搜索是一种分层的查找过程，每向前一层可能会访问一批顶点，不像深度优先搜索有回溯的过程。同时与深搜用栈来维护不同，广搜一般是用先进先出队列来进行维护的。实际上我们从初始状态开始，搜索第k层的意义就是，搜索需要k步才能到达的状态。广度优先搜索广度优先搜索是一种分层的查找过程，每向前一层可能广度优先搜索具体操作、特点具体操作：它是先将起始状态加入队列，然后每次从队列中取出一个状态，将其后继状态加入队列，后继状态指的是由当前状态一步操作可以到达的状态，直到所有状态均被访问为止。广度优先搜索具体操作、特点具体操作：广度优先搜索具

2、体操作、特点特点：1:它并不考虑结果的可能位置，而是彻底地搜索所有状态，所以很少有基于 BFS 的启发式算法，也很少对 BFS 进行剪枝。2:相对于 DFS，BFS 更加难于保存当前节点的状态，所以 BFS 在爆搜中的应用较少。广度优先搜索具体操作、特点3：在某一层还没有搜索完时，是不会进入下一层的，也就是说在队列中所有同一深度的状态，是连续的一段。（这个性质在之后会用到！）广度优先搜索具体操作、特点3：在某一层还没有搜索完时，是不会进入下一层的，也就是说在队经典例题1引出广度优先搜索给出一个n个点m条的边长均为1的无向图，求1到n的最短路。n=105，m=3*105经典例题1引出广度优先搜索

3、给出一个n个点m条的边长均为1最短路问题？迪杰斯特拉算法，spfa？有没有更快的做法？我们是不是要看一看题目有什么特殊性质。经典例题1引出广度优先搜索最短路问题？经典例题1引出广度优先搜索对于边长为1的最短路径问题，我们可以广度优先搜索，使复杂度变为O(N)，比迪杰斯特拉更加优。（重要套路！）我们来模拟一下这个过程。经典例题1引出广度优先搜索对于边长为1的最短路径问题，我们可以广度优先搜索，使复杂度变经典例题1引出广度优先搜索求1到n的最短路。最开始的时候将1号节点（初始状态）加入队列。作为第一层的元素。然后我们每一次会取出队首元素，扩展其相邻点，作为第2层。第二层：2、3。经典例题1引出广度

4、优先搜索求1到n的最短路。然后由第二层扩展第三层，不断重复取出队首元素，扩展相邻且未经过的点。第三层：4、5、6。第四层：7、8。第五层：9。这样我们就得到了9号节点到1号点的距离为4。经典例题1引出广度优先搜索然后由第二层扩展第三层，不断重复取出队首元素，扩展相邻且未经经典例题1代码实现经典例题1代码实现经典例题1代码实现注释在代码中。经典例题1代码实现注释在代码中。广搜一般的代码实现方式广搜一般的代码实现方式经典问题1的变形给出一个n个点m条的边长为0或者1的无向图，求1到n的最短路。n=105，m=3*105经典问题1的变形给出一个n个点m条的边长为0或者1的无向图，这也是一个比较经典的

5、技巧，同时也非常巧妙。提示：在新元素加进队列的时候，可不可以处理一下？经典问题1的变形这也是一个比较经典的技巧，同时也非常巧妙。经典问题1的变形我们考虑在遍历新的节点的时候，分边为0和1进行讨论。如果遍历过去经过0这条边，加到队首。如果遍历过去经过1这条边，加到队尾。然后就ok了。怎么这么简单？为什么？经典问题1的变形我们考虑在遍历新的节点的时候，分边为0和1进行讨论。经典问题实际上我们发现，整个这个队列中从前到后的点，就是按照和1号点距离从小到大排序的。而我们对于当前点u，新加进去的点v，如果边长度为0，那么v和u到1号点的距离相同，所以是要加到队首，在当前它是没有遍历到的点中距离1最近的。

6、经典问题1的变形实际上我们发现，整个这个队列中从前到后的点，就是按照和1号点而同理，如果是边长度为1，那当前肯定是距离1最远的，要加到队列的后面。经典问题1的变形经典问题1的变形对于这个队列的一些性质的证明1：对于每一时刻，队列中的所有点到1的距离，最大值和最小值最多相差1。2：队列内部的点，到1的距离是单调不下降的。3：我们每一次加进去一个点，一定是当前所能到达的点中距离1最远的。对于这个队列的一些性质的证明1：对于每一时刻，队列中的所有点经典问题2数联通块给出一个n*m的网格，每一个有一个颜色，两个格子之间相连当且仅当，两个格子相连且颜色相同。求联通块的数量。n*m=105经典问题2数联通

7、块给出一个n*m的网格，每一个有一个颜色举个例子：n=4 , m=51 2 1 2 3 1 1 1 2 32 2 2 2 33 3 3 3 3在这个问题中联通块的数量为4。经典问题2数联通块举个例子：经典问题2数联通块我们从上到下，从左到右，以此遍历每一个点，如果某一个点没有遍历到过，那么ans+，并遍历整个相邻的联通块。怎么代码实现？经典问题2数联通块我们从上到下，从左到右，以此遍历每一个点，如果某一个点没有遍经典问题2数联通块代码实现经典问题2数联通块代码实现有一个非常经典的编码技巧。对于当前所在的格子，你怎么遍历所有的相邻格子？QAQ：“4个if，枚举4个方向”其实有更简单办法，且拓展性

8、很强的方法。经典问题2数联通块一个代码技巧有一个非常经典的编码技巧。经典问题2数联通块一个代码图1：图2：经典问题2数联通块一个代码技巧图1：经典问题2数联通块一个代码技巧 我们发现，这样写，就可以用一个for循环，代替4个if。其实如果需要遍历8联通的格子，也是一样的。它的可拓展性非常强。经典问题2数联通块一个代码技巧 我们发现，这样写，就可以用一个for循环，代替4个if。经典问题3走迷宫给出一个n*m的网格，其中有一些格子是障碍“*”,不能经过，其他位置是空地“.”，初始时Bob被放在一个位置，求Bob最少走多少步可以走出网格。如果永远都不能走出网格，输出 -1 。n,m=1000经典问

9、题3走迷宫给出一个n*m的网格，其中有一些格子是障举个例子：一个5*5的迷宫，初始在S：(4,3)* * * * * . . . * . * . .* . S * .* * * * *红色的为走出迷宫的路线。经典问题3走迷宫举个例子：一个5*5的迷宫，初始在S：(4,3)经典问题3还是套用最开始给出的bfs的方法。最开始将初始坐标加入队列，然后每一次取出队首，扩展相邻没有遍历到过的点，然后加入队列中。如果某一时刻我们发现走出了网格了，那么直接输出当前的步数即可。如果队列空了，还是没有走出网格，说明无解，输出-1。经典问题3走迷宫还是套用最开始给出的bfs的方法。经典问题3走迷宫经典问题3走迷宫

10、代码实现经典问题3走迷宫代码实现八数码问题在33的棋盘上，摆有八个棋子，每个棋子上标有1至8的某一数字。棋盘中留有一个空格，空格用0来表示。空格周围的棋子可以移到空格中。要求解的问题是：给出一种初始布局（初始状态）和目标布局，找到一种最少步骤的移动方法，实现从初始布局到目标布局的转变。例：八数码问题在33的棋盘上，摆有八个棋子，每个棋子上标有1至八数码问题每一次移动算是一步，也就是说这是一个由初始状态到目标状态的所有边长均为1的最短路径问题。(这里状态指的是什么？)考虑bfs。实际上每一步，只需考虑空白格子和周围哪一个格子交换即可。咦？感觉交换两次可能会回到原先的状态？八数码问题每一次移动算是

11、一步，也就是说这是一个由初始状态到目需要对每一个局面进行hash。（用数字来表示这个局面，便于储存和判断）我们发现如果把三行拼在一起，那么这个棋盘就拼成了一个排列了。而排列和棋盘一一对应！计算可得：9!=362880。也就是说状态还是比较少的，对于排列的hash有一种很经典的方式叫做康拓展开。八数码问题需要对每一个局面进行hash。（用数字来表示这个局面，便于储康拓展开考虑一个0.(n-1)的排列 a0.(n-1)。HASH=a0*(n-1)!+a1*(n-2)!+.+a2*(n-3)!+.+an-1*0! ，其中ai为当前未出现的元素中是排在第几个(从0开始)。逆展开的话就是每次除以一个阶乘

12、，商为当前这个数是什么，余数则继续做下去。康拓展开考虑一个0.(n-1)的排列 a0.(n-1)康拓展开例子2 、0、 1展开= 2*2！ + 0 * 1！ + 0*0！同学们自己试一试3 、2、 0、 1的展开。这个康拓展开的本质是这个排列的字典序排名。康拓展开例子2 、0、 1展开对于0，1，2的排列，求3对应的排列。3/(2!) = 1 余1 1/(1!) =1 余 00/(0!)=0 余 0最后的答案是 1，2，0康拓逆展开例子对于0，1，2的排列，求3对应的排列。康拓逆展开例子codevs1004四子连棋在一个4*4的棋盘上摆放了14颗棋子，其中有7颗白色棋子，7颗黑色棋子，有两个空

13、白地带，任何一颗黑白棋子都可以向上下左右四个方向移动到相邻的空格，这叫行棋一步，黑白双方交替走棋，任意一方可以先走，如果某个时刻使得任意一种颜色的棋子形成四个一线（包括斜线），这样的状态为目标棋局。codevs1004四子连棋在一个4*4的棋盘上摆放了14颗是八数码问题的加强版。思路还是一样的，就是对于当前状态，我们看一看移动哪一个棋子就好。关键还是找一个hash函数，表示每一个状态。codevs1004四子连棋是八数码问题的加强版。codevs1004四子连棋hash函数：用一个二进制或者三进制来表示。代码怎么写？codevs1004四子连棋hash函数：用一个二进制或者三进制来表示。cod

14、evs10bzoj4395不太一样的bfs 有N*N个房间，组成了一张N*N的网格图，Bessie一开始位于左上角(1,1)，并且只能上下左右行走。 一开始，只有(1,1)这个房间的灯是亮着的，Bessie只能在亮着灯的房间里活动。 有另外M条信息，每条信息包含四个数a,b,c,d，表示房间(a,b)里有房间(c,d)的灯的开关。 请计算出最多有多少个房间的灯可以被打开bzoj4395不太一样的bfs 有N*N个房间在这个问题中我们需要考虑一下，什么样的格子，是可以遍历到的。1：与原先遍历到过的点相邻。2：这个格子的灯是开着的。这只有这两个条件满足时，我们才可以把一个格子加入队列里。bzoj4

15、395不太一样的bfs在这个问题中bzoj4395不太一样的bfs然后思路比较自然了。我们对于每一个格子记录是否与当前遍历到的格子相邻，以及是否亮灯。两种情况满足时，加入队列即可。bzoj4395不太一样的bfs然后思路比较自然了。bzoj4395不太一样的bfs双向广搜 所谓双向广搜，就是初始结点向目标结点和目标结点向初始结点同时扩展，直至在两个扩展方向上出现同一个结点，搜索结束。 普通的广搜是：从初始状态开始，一层一层不断扩展直到发现目标状态。 双向广搜：从初始和结束状态分别开始扩展，直到两方扩展的状态相遇。双向广搜 所谓双向广搜，就是初始结点向目标结双向广搜优点？ 速度快！我们用两张图来

16、对比一下。双向广搜优点？ 速度快！我们用两张图来对比一下。双向广搜优点？ 速度快！单向广搜的遍历空间：双向广搜优点？ 速度快！双向广搜优点？ 速度快！双向广搜的遍历空间：双向广搜优点？ 速度快！双向广搜缺点？主要是编码难度大，对代码能力的要求比较高。所以在考场上，如果时间没有那么充足，对双向广搜没有那么熟练的话，不建议写双广搜。双向广搜缺点？主要是编码难度大，对代码能力的要求比较高。双向广搜一般代码实现方式双向广搜一般代码实现方式双向广搜注意事项对于遍历，扩展节点时：要每次扩展一层，而不是每次扩展一个节点！反例？双向广搜注意事项对于遍历，扩展节点时：双向广搜注意事项双向广搜注意事项bzoj50

17、49Lydsy九月月赛导航系统这个国度由n座城市和m条双向道路构成。因为这个国度崇尚随机，因此m条边是用随机选择两端点的方式生成的。充满好奇的小Q想在这里进行k次随机的旅行，每次的起点和终点也是随机选择的。bzoj5049Lydsy九月月赛导航系统这个国度由n座bzoj5049Lydsy九月月赛导航系统在每次出发之前，他会使用导航系统计算两点间最少需要经过几条道路。请写一个程序，帮助小Q计算两点间的最短路。n=100000,m=300000,kB-C-D-E-F-G-I-J-H-K 每一次搜到底！深度优先搜索: A-B-C-D-E-F-G-I广度优先搜索 A- （第一层） B-E-K- （第二层）C-D-F-G-H （第三层）I-J （第四层） 一层一层搜索！广度优先搜索 A- （第一层）广搜广搜是一层一层，一步一步，所以很多求最短方案，最少的步骤数的搜索问题，考虑广搜。这种时候若用深搜，往往会没有一个明确的终止范围，容易搜索的过深，导致效率低下。广搜广搜是一层一层，一步一步，所以很多求最短方案，最少的步骤深搜深搜往往是把所有可行的情况列举出来了，找一个最优解，不一定是最短的步数。不是有的深搜也是求最短步数吗？注意广搜是一般不好加剪枝，但是深搜的剪枝使用比较方便，当搜索的界限比较明确，你也有一个比较成熟剪枝方案时，深搜是可以代替广搜找最短步数的。深搜深搜往往是把所有可行的