本文共 1665 字，大约阅读时间需要 5 分钟。

已经给定初始状态跟目标状态，要求之间的最短操作，其实也很明显是用BFS了。

我们把每次操作完的序列当做一个状态节点。那每一次操作就产生一条边，这个操作就是规则。

广度优先搜索（也称宽度优先搜索，缩写BFS，以下采用广度来描述）是的一种策略。因为它的思想是从一个顶点V0开始，辐射状地优先遍历其周围较广的区域，故得名。 

一般可以用它做什么呢？一个最直观经典的例子就是走迷宫，我们从起点开始，找出到终点的最短路程，很多最短路径算法就是基于广度优先的思想成立的。

******************************************

核心代码：

/**  * 广度优先搜索  * @param Vs 起点  * @param Vd 终点  */  bool BFS(Node& Vs, Node& Vd){      queue
   
     Q;      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;//无解  }
   

总结

假设图有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来判断是否已经被搜索过了。

转载地址：https://blog.csdn.net/weixin_38960774/article/details/79409987 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！