图的广度优先遍历

图的广度优先遍历

BFS 是一种用于解决==无权图最短路径==问题的算法。在无权图中，所有边的权重都相同，因此最短路径即为节点之间的最少跳数。

BFS 从源节点开始，==逐层遍历==邻居节点，直到遍历到目标节点或所有可达节点。通过记录每个节点的访问状态，可以确保每个节点只被访问一次。

通常使用==队列==来实现BFS。首先将源节点入队，然后循环执行以下步骤：从队列中取出一个节点，遍历其邻居节点，将未访问过的邻居节点标记为已访问，并将其加入队列。当队列为空时，算法结束。

1162. 地图分析

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

class Solution {
public:
    int rows;
    int columns;

    // 上右下左
    vector<int> move{-1, 0, 1, 0, -1};

    bool isCoordinateLegal(int row, int column) {
        return row >= 0 && row < rows && column >= 0 && column < columns;
    }

    // 多源 DFS
    int maxDistance(vector<vector<int>> &grid) {
        rows = grid.size();
        columns = grid[0].size();

        // 访问标记数组
        vector<vector<int>> visited(rows, vector<int>(columns, false));
        // 海洋个数
        int seas = 0;
        // 层级，由陆地向外扩展
        int lever = 0;
        // 存放到陆地的曼哈顿距离为 lever 的格子
        queue<pair<int, int>> q;
        for (int i = 0; i < rows; ++i) {
            for (int j = 0; j < columns; ++j) {
                if (grid[i][j] == 1) {
                    q.push(make_pair(i, j));
                    visited[i][j] = true;
                } else {
                    seas++;
                }
            }
        }
        // 全是海洋或陆地
        if (seas == 0 || seas == rows * columns) return -1;

        while (!q.empty()) {
            int size = q.size();
            // 同一层的一起出队
            for (int i = 0; i < size; ++i) {
                auto cod = q.front();
                q.pop();
                // 四周没处理过的入队
                for (int j = 0; j < 4; ++j) {
                    int x = cod.first + move[j];
                    int y = cod.second + move[j + 1];
                    if (!isCoordinateLegal(x, y) || visited[x][y]) continue;
                    q.push(make_pair(x, y));
                    visited[x][y] = true;
                }
            }
            lever++;
        }
        return lever - 1;
    }
};

691. 贴纸拼词

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <unordered_set>

using namespace std;

class Solution {
public:
    string getLeft(string target, string sticker) {
        string res = "";
        int len1 = target.length();
        int len2 = sticker.length();
        int i = 0, j = 0;
        while (i < len1 && j < len2) {
            if (target[i] == sticker[j]) {
                i++;
                j++;
            } else if (target[i] < sticker[j]) {
                // sticker 消除不了 target[i]
                res.append(1, target[i]);
                i++;
            } else {
                j++;
            }
        }

        // 剩余的都追加到 res
        if (i < len1) res.append(target, i, len1 - i + 1);

        return res;
    }

    int minStickers(vector<string> &stickers, string target) {
        vector<vector<string>> graph(26);
        // 避免相同的字符串再次入队重复处理
        unordered_set<string> visited;

        // 根据所有贴纸建图
        for (int i = 0; i < stickers.size(); ++i) {
            string str = stickers[i];
            // 贴纸里的字符排序
            sort(str.begin(), str.end());
            // u -> str:
            // 字符 u -> 能消去字符 u 的贴纸 str
            for (int j = 0; j < str.size(); ++j) {
                if (j == 0 || str[j] != str[j - 1])
                    graph[str[j] - 'a'].emplace_back(str);
            }
        }

        // 给定字符串里的字符排序
        sort(target.begin(), target.end());
        visited.emplace(target);
        // 层数就是要用掉的贴纸数
        int level = 1;
        // 存储等待删除字符的字符串
        queue<string> q;
        q.push(target);

        while (!q.empty()) {
            int len = q.size();
            // 每次处理一层
            for (int j = 0; j < len; ++j) {
                string str = q.front();
                q.pop();
                // 遍历所有能处理掉字符 str[0] 的字符串
                for (const auto &sticker: graph[str[0] - 'a']) {
                    // 获取剩余的字符串
                    string left = getLeft(str, sticker);
                    if (left == "") {
                        // 没有剩余的字符，说明目标字符串已经被消除光了
                        return level;
                    } else if (visited.find(left) == visited.end()) {
                        // 否则在之前没有加入队列的情况下，入队，等待使用其他贴纸进行消除
                        visited.emplace(left);
                        q.push(left);
                    }
                }
            }
            level++;
        }

        return -1;
    }
};

O1 BFS

• 适用于图中所有的==边的权值只有 0 和 1 两种值==，求源点到目标点的最短距离
• 时间复杂度：O(节点数量 + 边的数量)

• 流程：

  1. distance[i] 表示从源点到点 i 的最短距离，初始时所有点的 distance 设置为无穷大

  2. 源点进入双端队列，distance[源点] = 0

  3. 双端队列==头部弹出== x，

     A. 如果 x 为目标点，返回 distance[x] 表示源点到目标点的最短距离

     B. 考察从 x 出发的每条边，假设某条边去 y 点，边权重为 w

     ​ a. 如果 ==distance[y] > distance[x] + w==，更新 ==distance[y] = distance[x] + w==；同时如果 ==w 为 0，y 从头部进入==双端队列，==为 1 就从尾部进入==。重复步骤 3

     ​ b. 否则忽略该边，重复步骤 3

  4. 直到双端队列为空

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

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <unordered_set>

using namespace std;

class Solution {
public:
    int rows, columns;
    vector<int> move{-1, 0, 1, 0, -1};
    // 源点到目标点的距离
    vector<vector<int>> distance;

    bool isCoordinateLegal(int row, int column) {
        return row >= 0 && row < rows && column >= 0 && column < columns;
    }

    int minimumObstacles(vector<vector<int>> &grid) {
        rows = grid.size();
        columns = grid[0].size();
        // 初始距离都为无穷大
        distance.resize(rows, vector<int>(columns, INT_MAX));

        // 存储点的坐标
        deque<pair<int, int>> dq;
        dq.emplace_front(0, 0);
        // 源点到自身的距离为 0
        distance[0][0] = 0;

        while (!dq.empty()) {
            // 每次都从头部弹出
            auto point = dq.front();
            dq.pop_front();

            // 弹出的是目标点就返回最短距离
            if (point.first == rows - 1 && point.second == columns - 1)
                return distance[rows - 1][columns - 1];
            // 否则考察从 point 出发的每条边，假设某条边去点(x, y)，边权重为 weight
            for (int i = 0; i < 4; ++i) {
                int x = point.first + move[i];
                int y = point.second + move[i + 1];
                // 下标越界或者到达点(x, y)的距离无法通过点 point 变得更短，就跳过
                if (!isCoordinateLegal(x, y)
                    || distance[x][y] <= distance[point.first][point.second] + grid[x][y])
                    continue;
                // 更新成更短
                distance[x][y] = distance[point.first][point.second] + grid[x][y];
                if (grid[x][y] == 0)
                    // 边的权重为 0，放前面就能先出队列
                    dq.emplace_front(make_pair(x, y));
                else
                    dq.emplace_back(make_pair(x, y));
            }
        }
        return -1;
    }
};

1368. 使网格图至少有一条有效路径的最小代价

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <unordered_set>

using namespace std;

class Solution {
public:
    int rows, columns;
    vector<vector<int>> move = { {},
                                {0,  1},
                                {0,  -1},
                                {1,  0},
                                {-1, 0}};
    vector<vector<int>> distance;

    bool isCoordinateLegal(int row, int column) {
        return row >= 0 && row < rows && column >= 0 && column < columns;
    }

    int minCost(vector<vector<int>> &grid) {
        rows = grid.size();
        columns = grid[0].size();
        distance.resize(rows, vector<int>(columns, INT_MAX));

        deque<pair<int, int>> dq;
        dq.emplace_front(0, 0);
        distance[0][0] = 0;

        while (!dq.empty()) {
            auto point = dq.front();
            dq.pop_front();
            int x = point.first;
            int y = point.second;

            if (x == rows - 1 && y == columns - 1)
                return distance[rows - 1][columns - 1];
            for (int i = 1; i <= 4; ++i) {
                int nx = x + move[i][0];
                int ny = y + move[i][1];
                // 箭头和要走的方向一致，代价就是 0
                int cost = grid[x][y] == i ? 0 : 1;
                if (!isCoordinateLegal(nx, ny) || distance[nx][ny] <= distance[x][y] + cost)
                    continue;
                distance[nx][ny] = distance[x][y] + cost;
                if (cost == 0)
                    dq.emplace_front(nx, ny);
                else
                    dq.emplace_back(nx, ny);
            }
        }

        return -1;
    }
};

407. 接雨水 II

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <unordered_set>

using namespace std;

class Solution {
public:
    struct cmp {
        bool operator()(vector<int> &a, vector<int> &b) {
            return a[2] > b[2];
        }
    };

    int rows, columns;
    vector<int> move{-1, 0, 1, 0, -1};

    bool isCoordinateLegal(int row, int column) {
        return row >= 0 && row < rows && column >= 0 && column < columns;
    }

    int trapRainWater(vector<vector<int>> &heightMap) {
        rows = heightMap.size();
        columns = heightMap[0].size();

        // 标记是否已经放入堆中过
        vector<vector<bool>> visited;
        // 按照单元格高度排序
        priority_queue<vector<int>, vector<vector<int>>, cmp> heap;
        // 把矩阵四周放入堆，并且标记为访问过
        visited.resize(rows, vector<bool>(columns, false));
        for (int i = 0; i < rows; ++i) {
            for (int j = 0; j < columns; ++j) {
                if (i == 0 || i == rows - 1 || j == 0 || j == columns - 1) {
                    visited[i][j] = true;
                    heap.emplace(vector<int>{i, j, heightMap[i][j]});
                }
            }
        }

        int res = 0;
        while (!heap.empty()) {
            auto cur = heap.top();
            heap.pop();
            int x = cur[0];
            int y = cur[1];
            int w = cur[2];
            // w 只可能比 heightMap[x][y] 大，因为入堆的时候，选的就是较大值
            res += w - heightMap[x][y];

            for (int i = 0; i < 4; ++i) {
                int nx = x + move[i];
                int ny = y + move[i + 1];
                // 越界或者之前已经加入过堆中，就跳过
                if (!isCoordinateLegal(nx, ny) || visited[nx][ny]) continue;
                // 标记访问过了
                visited[nx][ny] = true;
                int nw = heightMap[nx][ny];
                // 为后续的格子提供的高度为当前高度和之前高度的较大值
                heap.emplace(vector<int>{nx, ny, max(w, nw)});
            }
        }
        return res;
    }
};

126. 单词接龙 II

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_set>
#include <unordered_map>

using namespace std;

class Solution {
public:
    unordered_set<string> dict;
    unordered_set<string> curLevel;
    // 为了去重，curLevel 中的多个字符串可能都能变成相同的字符串
    unordered_set<string> nextLevel;
    // 反向图：str 可以由 vector 中的字符串变动一个字符得到
    unordered_map<string, vector<string>> graph;
    // 结果
    vector<vector<string>> res;
    // 记录路径，每生成一条路径，加入到结果
    vector<string> path;

    void build(vector<string> &wordList) {
        for (const auto &item: wordList)
            dict.emplace(item);
    }

    // 一层层往下去建图，找到 target 时返回 true
    bool bfs(string wd, string target) {
        bool find = false;
        // 当前层加入 wd
        curLevel.emplace(wd);
        // 开始往下找由 wd 改变一个字符能得到的字符串 str，并将 str 放入 nextLevel
        while (!curLevel.empty()) {
            // 单词表删除当前层出现的单词，防止之后的某一层又出现相同的单词
            for (const auto &item: curLevel)
                dict.erase(item);
            for (string word: curLevel) {
                // nw 的每个位置，字符从 a 换到 z
                for (int i = 0; i < word.length(); ++i) {
                    // 新单词用于变换
                    string nw = word;
                    for (char ch = 'a'; ch <= 'z'; ch++) {
                        nw[i] = ch;
                        // 检查是否在单词表中出现过（排除原来的自己
                        if (dict.find(nw) != dict.end() && nw != word) {
                            // 找到目标单词
                            if (nw == target) find = true;
                            // 建立反向图，表示可以由 word 变动一个字符得到 nw
                            graph[nw].emplace_back(word);
                            // 追加到下一层，并且去重
                            nextLevel.emplace(nw);
                        }
                    }
                }
            }

            if (find == true) return true;
            swap(curLevel, nextLevel);
            nextLevel.clear();
        }
        return false;
    }

    void dfs(string wd, string target) {
        path.insert(begin(path), wd);
        if (wd == target) {
            res.emplace_back(path);
        } else if (graph.find(wd) != graph.end()) {
            // 倒过来往回找
            for (const auto &nxt: graph[wd])
                dfs(nxt, target);
        }
        // 回溯
        path.erase(begin(path));
    }

    vector<vector<string>> findLadders(string beginWord, string endWord, vector<string> &wordList) {
        build(wordList);
        if (dict.find(endWord) == dict.end()) return res;
        if (bfs(beginWord, endWord))
            // 由 endWord 找生成 beginWord 的路径
            dfs(endWord, beginWord);
        return res;
    }
};