1.前言广度优先搜索(也称宽度优先搜索,缩写BFS,以下采用广度来描述)是连通图的一种遍历策略。因为它的思想是从一个顶点V0开始,辐射状地优先遍历其周围较广的区域,故得名。 一般可以用它做什么呢?一个 广度/宽度优先搜索(BFS)
算法导论里边会给出不少严格的证明,我想尽量写得通俗一点,因此采用一些直观的讲法来伪装成证明,关键的point能够帮你get到就好。 2.图的概念刚刚说的广度优先搜索是连通图的一种遍历策略,那就有必要将图先简单解释一下。
图2-1连通图示例图 如图2-1所示,这就是我们所说的连通图,这里展示的是一个无向图,连通即每2个点都有至少一条路径相连,例如V0到V4的路径就是V0->V1->V4。 一般我们把顶点用V缩写,把边用E缩写。 3.广度优先搜索
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 | /** * 广度优先搜索 * @param Vs 起点 * @param Vd 终点 */ bool BFS(Node& Vs, Node& Vd){ queue Node Vn, Vw; int i; //用于标记颜色当visit[i][j]==true时,说明节点访问过,也就是黑色 bool visit[MAXL][MAXL]; //四个方向 int dir[][ 2 ] = { { 0 , 1 }, { 1 , 0 }, { 0 , - 1 }, {- 1 , 0 } }; //初始状态将起点放进队列Q Q.push(Vs); visit[Vs.x][Vs.y] = true ; //设置节点已经访问过了! while (!Q.empty()){ //队列不为空,继续搜索! //取出队列的头Vn Vn = Q.front(); Q.pop(); for (i = 0 ; i <> 4 ; ++i){ Vw = Node(Vn.x+dir[i][ 0 ], Vn.y+dir[i][ 1 ]); //计算相邻节点 if (Vw == Vd){ //找到终点了! //把路径记录,这里没给出解法 return true ; //返回 } if (isValid(Vw) && !visit[Vw.x][Vw.y]){ //Vw是一个合法的节点并且为白色节点 Q.push(Vw); //加入队列Q visit[Vw.x][Vw.y] = true ; //设置节点颜色 } } } return false ; //无解 } |
为了方便适用于大多数的题解,抽取核心代码如下:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 | /** * 广度优先搜索 * @param Vs 起点 * @param Vd 终点 */ bool BFS(Node& Vs, Node& Vd){ queue Node Vn, Vw; int i; //初始状态将起点放进队列Q Q.push(Vs); hash(Vw) = true ; //设置节点已经访问过了! while (!Q.empty()){ //队列不为空,继续搜索! //取出队列的头Vn Vn = Q.front(); //从队列中移除 Q.pop(); while (Vw = Vn通过某规则能够到达的节点){ if (Vw == Vd){ //找到终点了! //把路径记录,这里没给出解法 return true ; //返回 } if (isValid(Vw) && !visit[Vw]){ //Vw是一个合法的节点并且为白色节点 Q.push(Vw); //加入队列Q hash(Vw) = true ; //设置节点颜色 } } } return false ; //无解 } |
对于一个题目来说,要标志节点是否访问过,用数组是一种很快速的方法,但有时数据量太大,很难用一个大数组来记录时,采用hash是最好的做法。实际上visit数组在这里也是充当hash的作用。(PS:至于hash是什么?得自己去了解,它的作用是在O(1)的时间复杂度内取出某个值)
给定序列123456,再给定一个k,我们给出这样的操作:对于序列,我们可以将其中k个连续的数全部反转过来,例如k=3的时候,上述序列经过1步操作后可以变成:321456,如果再对序列321456进行一步操作,可以变成341256.
那么现在题目就是,给定初始序列,以及结束序列,以及k的值,那么你能够求出从初始序列到结束序列的转变至少需要几步操作吗?
本题可以采用BFS求解,已经给定初始状态跟目标状态,要求之间的最短操作,其实也很明显是用BFS了。
我们把每次操作完的序列当做一个状态节点。那每一次操作就产生一条边,这个操作就是规则。
假设起始节点是:{123456},终点是:{341256}
去除队列中的起始节点时,将它的相邻节点加入队列,其相邻节点就是对其操作一次的所有序列:
{321456}、{143256}、{125436}、{123654}
然后继续搜索即可得到终点,此时操作数就是搜索到的节点所在的层数2。
题目分类来自网络:
sicily:1048144412151135115011511114
pku:113612491028119132781426312630873414
假设图有V个顶点,E条边,广度优先搜索算法需要搜索V个节点,因此这里的消耗是O(V),在搜索过程中,又需要根据边来增加队列的长度,于是这里需要消耗O(E),总得来说,效率大约是O(V+E)。
其实最影响BFS算法的是在于Hash运算,我们前面给出了一个visit数组,已经算是最快的Hash了,但有些题目来说可能Hash的速度要退化到O(lgn)的复杂度,当然了,具体还是看实际情况的。
BFS适合此类题目:给定初始状态跟目标状态,要求从初始状态到目标状态的最短路径。
进而扩展的话就是双向广度搜索算法,顾名思义,即是从起点跟终点分别做广度优先搜索,直到他们的搜索过程中有一个节点相同了,于是就找到了起点跟终点的一条路径。
腾讯笔试题目:假设每个人平均是有25个好友,根据六维理论,任何人之间的联系一定可以通过6个人而间接认识,间接通过N个人认识的,那他就是你的N度好友,现在要你编程验证这个6维理论。
此题如果直接做广度优先搜索,那么搜索的节点数可能达到256,如果是用双向的话,两个树分别只需要搜索到3度好友即可,搜索节点最多为253个,但是用双向广度算法的话会有一个问题要解决,就是你如何在搜索的过程中判断第一棵树中的节点跟第二棵树中的节点有相同的呢?按我的理解,可以用Hash,又或者放进队列的元素都是指向原来节点的指针,而每个节点加入一个color的属性,这样再搜索过程中就可以根据节点的color来判断是否已经被搜索过了
|