时间复杂度
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(边数)。
核心代码
vector<vector<int>> EdgeToNeiBo(int n,const vector<vector<int>>& edges) { vector<vector<int>> vNeiB(n); for (const auto& v : edges) { vNeiB[v[0]].emplace_back(v[1]); vNeiB[v[1]].emplace_back(v[0]); } return vNeiB; } class CBFS1 { public: CBFS1(vector<vector<int>>& vNeiB, int s) { m_vDis.assign(vNeiB.size(), -1); m_vDis[s] = 0; vector<queue<int>> ques(vNeiB.size()); ques[0].emplace(s); for (int i = 1; (i < ques.size()) && ques[i - 1].size(); i++) { auto& pre = ques[i - 1]; while (pre.size()) { const int cur = pre.front(); pre.pop(); for (const auto next : vNeiB[cur]) { if (-1 != m_vDis[next]) { continue; } m_vDis[next] = m_vDis[cur] + 1; ques[i].emplace(next); } } } } public: vector<int> m_vDis; };
测试样例
#include <iostream> #include <vector> #include <queue> #include <assert.h> using namespace std; #define CBFS CBFS1 class CDebugBFS : public CBFS { public: using CBFS::CBFS1; void Assert(const vector<int>& vDis) { for (int i = 0; i < vDis.size(); i++) { assert(vDis[i] == m_vDis[i]); } } }; struct CDebugParam { int n; vector<vector<int>> edges; int s; vector<int> dis;//答案 }; int main() { vector<CDebugParam> 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。
class CBFS2 { public: CBFS2(vector<vector<int>>& vNeiB, int s) { m_vDis.assign(vNeiB.size(), -1); m_vDis[s] = 0; queue<int> pre; pre.emplace(s); for (int i = 1; pre.size(); i++) { queue<int> dp; while (pre.size()) { const int cur = pre.front(); pre.pop(); for (const auto next : vNeiB[cur]) { if (-1 != m_vDis[next]) { continue; } m_vDis[next] = m_vDis[cur] + 1; dp.emplace(next); } } dp.swap(pre); } } public: vector<int> m_vDis; };
一个队列就够了
由于是按从小到大入队，所以出队也是如此顺序。一个队列就够了。如果端点cur存在出边到达next，那么从s经过cur到达next的最短距离为dis[cur]+1。
class CBFS3 { public: CBFS3(vector<vector<int>>& vNeiB, int s) { m_vDis.assign(vNeiB.size(), -1); m_vDis[s] = 0; queue<int> que; que.emplace(s); while (que.size()) { const int cur = que.front(); que.pop(); for (const auto next : vNeiB[cur]) { if (-1 != m_vDis[next]) { continue; } m_vDis[next] = m_vDis[cur] + 1; que.emplace(next); } } } public: vector<int> m_vDis; };
测试环境
win10 VS2022 C++17
相关下载
相机源码下载
https://download.csdn.net/download/he_zhidan/88382037
其它
视频课程
如果你觉得复杂，想从简单的算法开始，可以学习我的视频课程。
https://edu.csdn.net/course/detail/38771
我的其它课程
https://edu.csdn.net/lecturer/6176
测试环境
win7 VS2019 C++17 或Win10 VS2022 Ck++17
相关下载
算法精讲《闻缺陷则喜算法册》doc版
