BFS

广度优先搜索BFSBY：唐灿,蔡东城图(Graph)是由有穷非空的顶点集合和一个描述顶点之间关系的边（或者弧）的集合组成。形式化定义：G＝（V，E）V为顶点集E为边(或者弧)集V1V2V4V5V3预备知识（1）无向图任意两个顶点构成的偶对(vi,vj)∈E是无序的，即顶点之间的连线是没有方向的,称为边(Edge)。（2）有向图任意两个顶点构成的偶对vi,vj∈E是有序的，即顶点之间的连线是有方向的，称为弧(Arc)。G1G2V1V3V2V4V1V3V2V4BFS基本思想：按层次来遍历搜索树1.从初始状态S开始，利用某种规则，生成所有可能的状态2.构成树的下一层节点，检查是否出现目标状态G，若未出现，就对该层所有状态节点利用这种规则生成下层的所有状态3.继续按上面思想生成再下一层的所有状态节点，这样一层一层往下展开。直到出现目标状态为止图解BFS:CEFIBDHG123456789BFS在访问了起始顶点A之后,由A出发,依次访问A的各个未被访问过的邻接顶点B,C,D,然后再顺序访问B,C,D的所有还未被访问过的邻接顶点。再从这些访问过的顶点出发，再访问它们的所有还未被访问过的邻接顶点，…如此做下去，直到图中所有顶点都被访问到为止。广度优先搜索是一种分层的搜索过程,每向前走一步可能访问一批顶点图解BFS：34252143628439585410696589710起点7终点1BFS实现方法：1.首先将根节点放入队列中。2.从队列中取出第一个节点，并检验它是否为目标。如果找到目标，则结束搜索并回传结果，否则将它所有尚未检验过的直接子节点加入队列中。3.若队列为空，表示整张图都检查过了——即图中没有欲搜索的目标。结束搜索并回传“找不到目标”，否则重复步骤2。BFS代码实现：时间复杂度和空间复杂度•时间复杂度：•O(|V|+|E|)：（没个节点最多访问一次，每条边最多访问一次)•空间复杂度：•O(|V|+|E|)。队列的基本用法：头文件：#includequeue常用函数：1.建立队列：queue元素类型队列名;2.向队列中(末尾)添加元素：队列名.push(元素名);3.去掉队列头元素：队列名.pop();4.队列头元素：队列名.front();5.判断是否为空：队列名.empty();6.队列大小：队列名.size();例题：PowerOJ1381Munching•链接：•题意：给你一个n*m的矩阵，每个位置只可能是“*”，“.”，“B”或者“C”，其中“*”表示是石头不能走，“.”表示草地可以走，问从“B”走到“C”至少需要走多少步。解决方法：BFS•假设图的每条边的权值都是1，由于BFS是分层进行的，所以，从起点到达同一层点的路经距离应该是相同的，如果在图中标记一个起点和一个终点，从起点出发，用BFS逐层向终点靠近，那么当到达终点时，会形成一条路径，那么这条路径必定是这两点的最短路经。我们先找到“B”点，然后以该坐标为起点去跑BFS，它的下一层的点就是该点的上下左右四个方向相邻的点，当遇到“C”就停止。为了方便起见，我们可以开个二维数组f[4][2]来表示四个方向，𝑓42=1,0,−1,0,0,1,0,−1，那么对于一个点𝑥,𝑦：（x+f[0][0],y+f[0][1])表示正下方（x+f[1][0],y+f[1][1])表示正上方（x+f[2][0],y+f[2][1])表示右方（x+f[3][0],y+f[3][1])表示左方我们在用的时候就只需要用一个for循环就能解决如图：P表示现在所在的节点next表示与它相邻的节点BFS部分代码：例题：HDU1548Astrangelift•链接：=1548•题意：•电梯每层有一个不同的数字，例如第n层有个数字k，那么这一层只能上k层或下k层，但是不能低于一层或高于n层，给定起点与终点，要求出最少要按几次键•样例：515（5层楼，求从1楼到5楼按电梯的次数）33125（每层的k值）答案：3（1→4→2→5）•问题分析：•我们用a数组来记录每一层的k值。•如果我们当前为x层，那么它下次只可能到x+a[x]层或者到x-a[x]层。(注意边界，不要越界)•那么这一题和上面的那道差不多就是一样的了。BFS部分代码：常见的BFS用法•1.普通BFS•2.双向BFS双向BFS：•如果已经知道搜索的开始状态和结束状态，要找一个满足某种条件的一条路径（一般是最短路径），为了避免无谓的“组合爆炸”产生，就可以采取双向广度搜索算法，也就是从开始状态和结束状态同时开始搜索，一个向前搜，一个向后找。双向BFS的实现：•双向BFS算法的实质还是BFS，只不过两边同时开始BFS而已。还是可以利用队列来实现：可以设置两个队列，一个用于向前的BFS，另一个用于向后的BFS，利用这两个队列，同时从前、后开始层次遍历搜索树。双向BFS的好处双向BFS的好处END