左程云算法 BFS

宽度优先遍历及其扩展

BFS

Posted by Marlin on August 27, 2025

宽度优先遍历及其扩展

宽度优先遍历基本内容

bfs 的特点是逐层扩散,从源头点到目标点扩散了几层,最短格就是多少
bfs 可以使用的特征是任意两个节点之间的相互距离相同（无向图）
bfs 开始时,可以是单个源头、也可以是多个源头
bfs 频繁使用队列,形式可以是单点弹出或者整层弹出
bfs 进行时,进入队列的节点需要标记状态,防止同一个节点重复进出队列
bfs 进行时,可能会包含剪枝策略的设计

bfs 是一个理解难度很低的算法,难点在于节点如何找到路、路的展开和剪枝设计

题目 1 地图分析

多源 BFS

思路：

  • 将所有海洋点加入队列
  • 队列中弹出一个点，将其上下左右四个方向的点加入队列，维护最大距离
  • 重复上述操作，直到队列为空
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

static const int N = 1e3 + 10;
int n, m;
int ans;
int vis[N][N];
int dx[4] = {0, 1, 0, -1};
int dy[4] = {-1, 0, 1, 0};
queue<tuple<int, int, int>> que;
void bfs() {
    while (!que.empty()) {
        auto [x, y, cnt] = que.front();
        que.pop();
        for (int i = 0; i < 4; i++) {
            int a = x + dx[i];
            int b = y + dy[i];
            if (a < 0 || b < 0 || a >= n || b >= m) {
                continue;
            }
            if (vis[a][b]) {
                continue;
            }
            vis[a][b] = 1;
            ans = max(ans, cnt + 1);
            que.push({a, b, cnt + 1});
        }
    }
}
int maxDistance(vector<vector<int>> &grid) {
    grid = grid;
    n = grid.size();
    m = grid[0].size();
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (grid[i][j] == 1) {
                vis[i][j] = 1;
                que.push({i, j, 1});
            }
        }
    }
    bfs();
    return ans - 1;
}

题目 2 贴纸拼词

思路：

  • 排序所有贴纸单词和目标单词，使得字母按顺序排列
  • 为每个字母(a-z)建立索引，收集所有包含该字母的贴纸，形成字母-贴纸的映射关系
  • 广度优先搜索，每次搜索一个字母，将所有能拼出目标单词的贴纸单词加入队列，并标记为已访问
  • 重复上述操作，直到队列为空
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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

static const int N = 410;
queue<string> que;
unordered_set<string> visited;
vector<vector<string>> g;
string getnext(string cur, string s) {
    string res;
    int l = 0;
    int r = 0;
    while (l < cur.size() && r < s.size()) {
        if (cur[l] == s[r]) {
            l++;
            r++;
        } else if (cur[l] < s[r]) {
            res += cur[l];
            l++;
        } else {
            r++;
        }
    }
    while (l < cur.size()) {
        res += cur[l++];
    }
    return res;
}
int minStickers(vector<string> &stickers, string target) {
    g.resize(N);
    sort(target.begin(), target.end());
    for (auto &sticker : stickers) {
        sort(sticker.begin(), sticker.end());
    }
    // 建图
    for (int i = 0; i < stickers.size(); i++) {
        unordered_set<char> temp;
        for (int j = 0; j < stickers[i].size(); j++) {
            if (temp.count(stickers[i][j]) == 0) {
                int idx = stickers[i][j] - 'a';
                temp.insert(stickers[i][j]);
                g[idx].push_back(stickers[i]);
            }
        }
    }
    visited.insert(target);
    que.push(target);
    int level = 1;
    while (!que.empty()) {
        int size = que.size();
        for (int i = 0; i < size; i++) {
            string cur = que.front();
            que.pop();
            for (string s : g[cur[0] - 'a']) {
                string next = getnext(cur, s);
                if (next == "") {
                    return level;
                } else if (!visited.count(next)) {
                    visited.insert(next);
                    que.push(next);
                }
            }
        }
        level++;
    }
    return -1;
}

01BFS

01bfs,适用于图中所有边的权重只有 0 和 1 两种值,求源点到到目标点的最短距离
时间复杂度为O(节点数量+边的数量),为什么不能用传统 bfs?
过程:

  1. distance[i]表示从源点到 i 点的最短距离,初始时所有点的distance设置为无穷大
  2. 源点进入双端队列,distance[源点] = 0
  3. 双端队列头部弹出x,
    1. 如果 x 是目标点,返回distance[x]表示源点到目标点的最短距离
    2. 考察从 x 出发的每一条边,假设某边去 y 点,边权为 w
      1. 如果distance[y] > distance[x] + w,处理该边;否则忽略该边
      2. 处理时,更新distance[y] = distance[x] + w
        如果w == 0,y 从头部进入双端队列。继续重复步骤 3
        如果w == 1,y 从尾部进入双端队列。继续重复步骤 3
  4. 双端队列为空停止

题目 3 到达角落需要移除障碍物的最小数目

思路：

  • 01BFS，墙壁用 1 表示，空地用 0 表示
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

int dx[4] = {0, 1, 0, -1};
int dy[4] = {-1, 0, 1, 0};
int minimumObstacles(vector<vector<int>> &grid) {
    int m = grid.size();
    int n = grid[0].size();
    vector<vector<int>> distance(m, vector<int>(n, INT_MAX));
    deque<pair<int, int>> dque;
    dque.push_back({0, 0});
    distance[0][0] = 0;
    while (!dque.empty()) {
        auto [x, y] = dque.front();
        dque.pop_front();
        if (x == m - 1 && y == n - 1) {
            return distance[x][y];
        }
        for (int i = 0; i < 4; i++) {
            int a = x + dx[i];
            int b = y + dy[i];
            if (a < 0 || b < 0 || a >= m || b >= n) {
                continue;
            }
            if (distance[a][b] <= distance[x][y] + grid[a][b]) {
                continue;
            }
            distance[a][b] = distance[x][y] + grid[a][b];
            if (grid[a][b] == 1) {
                dque.push_back({a, b});
            } else {
                dque.push_front({a, b});
            }
        }
    }
    return -1;
}

题目 4 使网课图至少有一条有效路径的最小代价

思路：

  • 01BFS，箭头指向的位置记为 0，否则为 1。
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

int dx[5] = {0, 0, 0, 1, -1}; // 1右 2左 3下 4上
int dy[5] = {0, 1, -1, 0, 0};
int minCost(vector<vector<int>> &grid) {
    int m = grid.size();
    int n = grid[0].size();
    vector<vector<int>> distance(m, vector<int>(n, INT_MAX));
    deque<pair<int, int>> dque;
    dque.push_back({0, 0});
    distance[0][0] = 0;
    while (!dque.empty()) {
        auto [x, y] = dque.front();
        dque.pop_front();
        if (x == m - 1 && y == n - 1) {
            return distance[x][y];
        }
        for (int i = 1; i <= 4; i++) {
            int a = x + dx[i];
            int b = y + dy[i];
            int w = grid[x][y] == i ? 0 : 1; // 箭头指向i位置为0，否则为1
            if (a < 0 || b < 0 || a >= m || b >= n) {
                continue;
            }
            if (distance[a][b] <= distance[x][y] + w) {
                continue;
            }
            distance[a][b] = distance[x][y] + w;
            if (w == 1) {
                dque.push_back({a, b});
            } else {
                dque.push_front({a, b});
            }
        }
    }
    return -1;
}

BFS 与优先队列结合

宽度优先遍历与深度优先遍历结合,去生成路径

  1. bfs 建图
  2. dfs 利用图生成路径

题目 5 二维接雨水

思路：
二维接雨水的核心在于“木桶原理”：

一个格子最终能积多少水，由包围它的、最低的那一圈边界决定。
因此不能简单地看四周相邻格子的原始高度，而要动态地把“已经处理过的、可能成为边界”的格子都考虑进来。

主流做法是“最小堆 + BFS”，把一维双指针/单调栈的思想推广到二维空间：

  1. 把矩阵最外圈全部入堆
    这些格子不可能存水，但它们是初始“围墙”。
    堆中保存的是“当前已知边界高度”，而非格子原始高度。
  2. 不断取出当前最低的边界高度 w 及其坐标 (x,y)
    水总是从最矮的“缺口”先溢出。
  3. 四方向扩展邻居 (a,b)
    • 若邻居已访问 → 跳过
    • 否则：
      – 计算邻居的新边界高度：newH = max(heightMap[a][b], w)
      – 若邻居原始高度 heightMap[a][b] < w → 可积水 ans += w - heightMap[a][b]
      – 把邻居标记为已访问，并将 (a,b,newH) 入堆
      （此后该邻居的边界高度就是 newH，与原始 heightMap[a][b] 无关）
  4. 重复直到堆空，累加的量就是答案。
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

struct Cmp {
    bool operator()(const tuple<int, int, int> &a,
                    const tuple<int, int, int> &b) {
        return get<2>(a) > get<2>(b);
    }
};
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, Cmp>
    heap;
int trapRainWater(vector<vector<int>> &heightMap) {
    int n = heightMap.size();
    int m = heightMap[0].size();
    vector<vector<bool>> visited(n, vector<bool>(m, false));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (i == 0 || j == 0 || i == n - 1 || j == m - 1) {
                heap.push({i, j, heightMap[i][j]});
                visited[i][j] = true;
            } else {
                visited[i][j] = false;
            }
        }
    }
    int ans = 0;
    while (!heap.empty()) {
        auto [x, y, w] = heap.top();
        heap.pop();
        ans += w - heightMap[x][y];
        for (int i = 0; i < 4; i++) {
            int a = x + dx[i];
            int b = y + dy[i];
            if (a < 0 || b < 0 || a >= n || b >= m) {
                continue;
            }
            if (visited[a][b]) {
                continue;
            }
            heap.push({a, b, max(heightMap[a][b], w)});
            visited[a][b] = true;
        }
    }
    return ans;
}

题目 6 单词接龙 II

思路：

双向 BFS 建图 + DFS 回溯输出所有最短路径

但这里实现的是单向 BFS，并且用了两个技巧来只保留最短路径：

1️⃣ 数据结构总览

名称 作用
dict 未访问的单词集合（在 BFS 的每一层开始前把当前层节点删掉）
curLevel / nextLevel 当前层 / 下一层节点，层序推进
g[word] 记录 word 能一步到达的所有单词（只记录最短路径上的边）
path / ans DFS 回溯用的临时路径 / 最终答案

2️⃣ BFS 阶段（函数 bfs）

目标：按层扩散，第一次碰到 endWord 时立即返回，此时 g 里只保留了最短路径上的边。

  • 逐层删词：

    每进入下一层前，把 curLevel 里的词从 dict 中删掉，防止出现环或更长的路径。

  • 建图：

    如果 str 在 dict 中且 str != word，则 g[word].push_back(str)，并把 str 加入 nextLevel。注意这里的 g 只建了“最短路径”上的边，因为一旦发现 str == endWord，就立即 return true，后续更深的层不会再扩展。

  • 提前终止：

    find = true 时立刻返回，保证 BFS 只跑到最短长度那一层。

3️⃣ DFS 阶段（函数 dfs）

  • 从 beginWord 开始，按 g 里的邻接表深度优先遍历，所有走到 endWord 的路径长度恰好是最短步数（因为 BFS 只保留了这些边）。
  • 回溯时 path.pop_back() 恢复现场。

4️⃣ 主函数 findLadders

  1. 把所有词装进 dict。
  2. 如果 endWord 不在 dict，直接返回空。
  3. 调用 bfs 建图；若返回 true，则调用 dfs 收集所有解。

5️⃣ 时间复杂度

  • BFS：O(M * 26 * N)，其中 M 为单词长度，N 为单词数。
  • DFS：最坏 O(所有最短路径数 × 路径长度)。

6️⃣ 一句话总结

用“逐层删词”的单向 BFS 确保只建最短路径图，再用 DFS 回溯输出所有最短路。

TLE 做法：

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

unordered_set<string> dict, curLevel, nextLevel;
unordered_map<string, vector<string>> g;
vector<string> path;
vector<vector<string>> ans;
bool bfs(string begin, string end) {
    bool find = false;
    curLevel.insert(begin);
    while (!curLevel.empty()) {
        for (auto it : curLevel) {
            dict.erase(it);
        }
        for (string word : curLevel) {
            string w = word;
            for (int i = 0; i < w.size(); i++) {
                char old = w[i];
                for (char ch = 'a'; ch <= 'z'; ch++) {
                    w[i] = ch;
                    string str = w;
                    if (dict.count(str) && str != word) {
                        if (str == end) {
                            find = true;
                        }
                        g[word].push_back(str);
                        nextLevel.insert(str);
                    }
                }
                w[i] = old;
            }
        }
        if (find) {
            return true;
        } else {
            swap(curLevel, nextLevel);
            nextLevel.clear();
        }
    }
    return false;
}
void dfs(string word, string aim) {
    path.push_back(word);
    if (word == aim) {
        ans.push_back(path);
    } else if (g.count(word)) {
        for (auto next : g[word]) {
            dfs(next, aim);
        }
    }
    path.pop_back();
}
vector<vector<string>> findLadders(string beginWord, string endWord,
                                    vector<string> &wordList) {
    for (auto word : wordList) {
        dict.insert(word);
    }
    if (!dict.count(endWord)) {
        return ans;
    }
    if (bfs(beginWord, endWord)) {
        dfs(beginWord, endWord);
    }
    return ans;
}
CATALOG
    FEATURED TAGS
    Markdown 左程云算法 图论 位运算 二进制 二叉树 堆结构 对拍 对数器 并查集 拓扑排序 蓝桥杯 个人简历 分治 双向广搜 反思 同余原理 埃氏筛 基数排序 堆排序 子集枚举 字符串 岁末书 建图 建模纪事 异或 归并分治 归并排序 感想 排列 排序 排序算法 攻略 数据库 数论 时间复杂度 最大公约数 最小生成树 最近公共祖先 欧拉筛 正则表达式 竞赛总结 素数筛 线性筛 组合 自定义比较规则 荷兰国旗 试除法 递归 邻接矩阵 邻接表 链式前向星 随机快速排序 随机选择算法 BFS CET DFS DHCP Flood Fill Git Hello IP冲突 LCA SQL STL WLAN bitset luogu
    FRIENDS