C++算法：广度优先搜索(BFS)的原理和实现

时间复杂度

O(m) ,m是边的数量。许多经典应用场景，如2D游戏地图、网格，出边固定不超过4或8(4联通或8联通），这种情况也可以说BFS的时间复杂度是O(n)，n是端点数。
每个端点只会访问一次，显然第一次访问的是最小距离，第二次访问时距离只会变大或不变，没有继续访问的意义。假定s到x2的最短最短距离经过x1，如果s到x1距离变大，x1到x2的距离不变，则s到x2的距离变大。

使用前提

各边的权重都为1。

典型场景

n个端点的无向图，编号范围[0,n)。每个端点最多4条出边。edges表示{{n1,n2},...{n3,n4}}表示n1和n2，n3和n4之间有边联接。求s到d的最少需要经过多少条边。如果无法到达，请返回-1。可能有环，但无自环，重边，可能不联通。

可理解性强的解法

Dis数组记录源点到各点的最短距离，初始-1，表示无法从源点到达当前点。不为-1，表示当前是第二次访问，无需处理。队列向量的元素que[i]记录经过i条边可以到达的点。分两步：一，将边转成邻接表；二，三层循环处理最短距离。第一层循环通过que[i-1]计算que[i]，如果que[i]为空，提前结束。经过i条边无法到达任意点，则经过i+1条边，也无法达到任意点。已经处理的端点不用入队；第二层循环遍历que[i]；第三层遍历当前点的出边。因为不会处理重复的点，所以第一层循环和第二层循环合起来，时间复杂度是O(边数)。

核心代码

  1. vectorint>> EdgeToNeiBo(int n,const vectorint>>& edges)
  2. {
  3.     vectorint>> vNeiB(n);
  4.     for (const auto& v : edges)
  5.     {
  6.         vNeiB[v[0]].emplace_back(v[1]);
  7.         vNeiB[v[1]].emplace_back(v[0]);
  8.     }
  9.     return vNeiB;
  10. }
  11. class CBFS1
  12. {
  13. public:
  14.     CBFS1(vectorint>>& vNeiB, int s)
  15.     {
  16.         m_vDis.assign(vNeiB.size(), -1);
  17.         m_vDis[s] = 0;
  18.         vectorint>> ques(vNeiB.size());
  19.         ques[0].emplace(s);
  20.         for (int i = 1; (i < ques.size()) && ques[i - 1].size(); i++)
  21.         {
  22.             auto& pre = ques[i - 1];
  23.             while (pre.size())
  24.             {
  25.                 const int cur = pre.front();
  26.                 pre.pop();
  27.                 for (const auto next : vNeiB[cur])
  28.                 {
  29.                     if (-1 != m_vDis[next])
  30.                     {
  31.                         continue;
  32.                     }
  33.                     m_vDis[next] = m_vDis[cur] + 1;
  34.                     ques[i].emplace(next);
  35.                 }
  36.             }
  37.         }
  38.     }
  39. public:
  40.     vector<int> m_vDis;
  41. };

测试样例

#include
#include
#include
#include
using namespace std;

#define CBFS CBFS1 

class CDebugBFS : public CBFS
{
public: 
    using CBFS::CBFS1;
    void Assert(const vector& vDis)
    {
        for (int i = 0; i < vDis.size(); i++)
        {
            assert(vDis[i] == m_vDis[i]);
        }
    }
};

struct CDebugParam
{
    int n;
    vector> edges;
    int s;
    vector dis;//答案
};

int main()
{
    vector params = { {1,{},0,{0}},{2,{},0,{0,-1}},
    {6,{{0,1},{1,2},{1,3},{2,4},{4,5},{3,5}},0,{0,1,2,2,3,3} }
};
    for (const auto& par : params)
    {
        auto vNeiB = EdgeToNeiBo(par.n, par.edges);
        CDebugBFS bfs(vNeiB,par.s);
        bfs.Assert(par.dis);
    }    
}

滚动队列优化

由于每次循环都只涉及que[i]和que[i-1]，可以用que和pre代替，循环结束swap。

  1. class CBFS2
  2. {
  3. public:
  4.     CBFS2(vectorint>>& vNeiB, int s)
  5.     {
  6.         m_vDis.assign(vNeiB.size(), -1);
  7.         m_vDis[s] = 0;
  8.         queue<int> pre;
  9.         pre.emplace(s);
  10.         for (int i = 1; pre.size(); i++)
  11.         {
  12.             queue<int> dp;
  13.             while (pre.size())
  14.             {
  15.                 const int cur = pre.front();
  16.                 pre.pop();
  17.                 for (const auto next : vNeiB[cur])
  18.                 {
  19.                     if (-1 != m_vDis[next])
  20.                     {
  21.                         continue;
  22.                     }
  23.                     m_vDis[next] = m_vDis[cur] + 1;
  24.                     dp.emplace(next);
  25.                 }
  26.             }
  27.             dp.swap(pre);
  28.         }
  29.     }
  30. public:
  31.     vector<int> m_vDis;
  32. };

一个队列就够了

由于是按从小到大入队，所以出队也是如此顺序。一个队列就够了。如果端点cur存在出边到达next，那么从s经过cur到达next的最短距离为dis[cur]+1。

  1. class CBFS3
  2. {
  3. public:
  4.     CBFS3(vectorint>>& vNeiB, int s)
  5.     {
  6.         m_vDis.assign(vNeiB.size(), -1);
  7.         m_vDis[s] = 0;
  8.         queue<int> que;
  9.         que.emplace(s);
  10.         while (que.size())
  11.         {
  12.             const int cur = que.front();
  13.             que.pop();
  14.             for (const auto next : vNeiB[cur])
  15.             {
  16.                 if (-1 != m_vDis[next])
  17.                 {
  18.                     continue;
  19.                 }
  20.                 m_vDis[next] = m_vDis[cur] + 1;
  21.                 que.emplace(next);
  22.             }
  23.         }
  24.     }
  25. public:
  26.     vector<int> m_vDis;
  27. };

测试环境

win10  VS2022  C++17

相关下载


相机源码下载
https://download.csdn.net/download/he_zhidan/88382037
 

https://img-blog.csdnimg.cn/ea2601b3918f4aef836b5fe30da2ebf7.gif#pic_center#pic_center

其它

视频课程

如果你觉得复杂，想从简单的算法开始，可以学习我的视频课程。

https://edu.csdn.net/course/detail/38771

我的其它课程

https://edu.csdn.net/lecturer/6176

测试环境

win7 VS2019 C++17 或Win10 VS2022 Ck++17

相关下载

算法精讲《闻缺陷则喜算法册》doc版

https://download.csdn.net/download/he_zhidan/88348653

作者人生格言

有所得，以墨记之，故曰墨家

闻缺陷则喜。问题发现得越早，越给老板省钱。

算法是程序的灵魂

https://img1.iyenn.com/thumb02/c4a7c45db2a7b21g/98031697456709977022.jpeg

文章知识点与官方知识档案匹配，可进一步学习相关知识
算法技能树首页概览60496 人正在系统学习中
群中有博文配套源码
QQ群名片
注：本文转载自blog.csdn.net的闻缺陷则喜何志丹的文章"https://blog.csdn.net/he_zhidan/article/details/133380813"。版权归原作者所有，此博客不拥有其著作权，亦不承担相应法律责任。如有侵权，请联系我们删除。
复制链接
相关推荐
发表评论

评论记录：

未查询到任何数据！