图论-广度优先遍历及其拓展

package BFS;

public class Code01_BFS {
    public static int MAXN = 1001;
    public static int MAXM = 2003;
    public static int[] head = new int[MAXN];
    public static int[] next = new int[MAXM];
    public static int[] to = new int[MAXM];
    public static int cnt;
    public static int[] queue = new int[MAXN];
    public static int l, r;
    public static boolean[] visited = new boolean[MAXN];

    // 把 0 编号空出来
    public static void build(int n) {
        for (int i = 1; i <= n; i++) {
            head[i] = 0;
            visited[i] = false;
        }
        cnt = 1;
    }

    // 添加一条有向边 u -> v
    // 无向边就交换参数多调一次
    public static void addEdge(int u, int v) {
        next[cnt] = head[u];
        to[cnt] = v;
        head[u] = cnt++;
    }

    public static void bfs(int start) {
        if (start == 0) return;
        queue[r++] = start;
        visited[start] = true;
        while (l != r) {
            int cur = queue[l++];
            System.out.print(cur + " ");
            for (int ei = head[cur]; ei != 0; ei = next[ei]) {
                int dst = to[ei];
                if (!visited[dst]) {
                    queue[r++] = dst;
                    visited[dst] = true;
                }
            }
        }
    }

    public static void main(String[] args) {
        build(6);
        addEdge(1, 2); addEdge(1, 3);
        addEdge(2, 4); addEdge(2, 5);
        addEdge(3, 6);
        System.out.println("BFS traversal starting from node 1:");
        bfs(1);
    }
}

Code02_BFS_Matrix.javajava

package BFS;

public class Code02_BFS_Matrix {
    public static int MAXN = 101;
    public static int[][] graph = new int[MAXN][MAXN];
    public static int[] queue = new int[MAXN];
    public static int l, r;
    public static boolean[] visited = new boolean[MAXN];
    public static int n;

    public static void build() {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) graph[i][j] = 0;
            visited[i] = false;
        }
    }

    public static void addEdge(int u, int v) {
        graph[u][v] = 1;
    }

    public static void bfs(int start) {
        if (start == 0) return;
        queue[r++] = start;
        visited[start] = true;
        while (l != r) {
            int cur = queue[l++];
            System.out.print(cur + " ");
            for (int next = 1; next <= n; next++) {
                if (graph[cur][next] == 1 && !visited[next]) {
                    queue[r++] = next;
                    visited[next] = true;
                }
            }
        }
    }

    public static void main(String[] args) {
        n = 6;
        build();
        addEdge(1, 2); addEdge(1, 3);
        addEdge(2, 4); addEdge(2, 5);
        addEdge(3, 6);
        System.out.println("BFS traversal starting from node 1:");
        bfs(1);
    }
}

Code03_BFS_List.javajava

package BFS;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Queue;

public class Code03_BFS_List {
    public static ArrayList<ArrayList<Integer>> graph = new ArrayList<>();

    public static void build(int n) {
        graph.clear();
        for (int i = 0; i <= n; i++) graph.add(new ArrayList<>());
    }

    public static void addEdge(int u, int v) {
        graph.get(u).add(v);
    }

    public static void bfs(int start) {
        if (start == 0) return;
        Queue<Integer> queue = new ArrayDeque<>();
        HashSet<Integer> set = new HashSet<>();
        queue.add(start);
        set.add(start);
        while (!queue.isEmpty()) {
            int cur = queue.poll();
            System.out.print(cur + " ");
            for (int next : graph.get(cur)) {
                if (!set.contains(next)) {
                    set.add(next);
                    queue.add(next);
                }
            }
        }
    }

    public static void main(String[] args) {
        build(6);
        addEdge(1, 2); addEdge(1, 3);
        addEdge(2, 4); addEdge(2, 5);
        addEdge(3, 6);
        System.out.println("BFS traversal starting from node 1:");
        bfs(1);
    }
}

三种建图怎么选？

链式前向星：竞赛/算法题首选，数组实现快、内存可控
邻接矩阵：稠密图（边数 ≈ $V^2$ ）或需要 $O(1)$ 查询某条边是否存在
邻接表：工程代码、节点稀疏、写起来直观

按层 BFS（Level-Order BFS）

朴素 BFS 不区分层，按层 BFS 显式地把层切分出来。这是树的层序遍历的图论推广。

关键技巧

在每轮 while 循环开始时，先记录当前队列大小 size，然后只处理这 size 个节点——它们就是同一层。

按层模板java

public static int bfsByLevel(int start) {
    Queue<Integer> queue = new ArrayDeque<>();
    boolean[] visited = new boolean[MAXN];
    queue.add(start);
    visited[start] = true;

    int level = 0;
    while (!queue.isEmpty()) {
        int size = queue.size();      // ⭐ 锁定当前层节点数
        for (int i = 0; i < size; i++) {
            int cur = queue.poll();
            // 处理同层节点 cur，level 即它所在层
            for (int next : graph.get(cur)) {
                if (!visited[next]) {
                    visited[next] = true;
                    queue.add(next);
                }
            }
        }
        level++;                      // ⭐ 这一层处理完，层号 +1
    }
    return level;
}

例题：LeetCode 102. 二叉树的层序遍历

🌲 LeetCode 102 完整代码

LC102.javajava

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ans = new ArrayList<>();
        if (root == null) return ans;
        Deque<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> level = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                TreeNode cur = queue.poll();
                level.add(cur.val);
                if (cur.left != null) queue.offer(cur.left);
                if (cur.right != null) queue.offer(cur.right);
            }
            ans.add(level);
        }
        return ans;
    }
}

例题：LeetCode 127. 单词接龙

🔤 LeetCode 127 思路+代码

思路：把每个单词当作图的节点，相差一个字母的两个单词之间有一条边。从 beginWord 到 endWord 的最少转换次数 = BFS 的最少层数 + 1。

优化建图：不要两两枚举单词建图（ $O(N^2 \cdot L)$ ）。改用虚拟节点：单词 hot 与 *ot/h*t/ho* 三个虚拟节点相连。

LC127.javajava

class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        Set<String> dict = new HashSet<>(wordList);
        if (!dict.contains(endWord)) return 0;

        Queue<String> queue = new ArrayDeque<>();
        Set<String> visited = new HashSet<>();
        queue.offer(beginWord);
        visited.add(beginWord);

        int level = 1;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                String cur = queue.poll();
                if (cur.equals(endWord)) return level;
                char[] chars = cur.toCharArray();
                for (int j = 0; j < chars.length; j++) {
                    char origin = chars[j];
                    for (char c = 'a'; c <= 'z'; c++) {
                        if (c == origin) continue;
                        chars[j] = c;
                        String next = new String(chars);
                        if (dict.contains(next) && !visited.contains(next)) {
                            visited.add(next);
                            queue.offer(next);
                        }
                    }
                    chars[j] = origin;
                }
            }
            level++;
        }
        return 0;
    }
}

多源 BFS（Multi-Source BFS）

什么是多源 BFS？

多个起点同时出发，求所有节点到"任意一个起点"的最短距离（边数）。

核心技巧

把所有源点一次性全部入队，然后跑普通 BFS。神奇的是——队列里同时存在的节点们，"距离最近的某个源点的层数"是相同的。

为什么这是对的？想象虚拟超级源点 $S$ ，它向所有真实源点连一条权 0 的边。从 $S$ 出发的 BFS = 把所有真实源点同时入队的 BFS。

例题：LeetCode 994. 腐烂的橘子

🍊 LeetCode 994 完整代码

LC994.javajava

class Solution {
    public int orangesRotting(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        Deque<int[]> queue = new ArrayDeque<>();
        int fresh = 0;

        // ⭐ 把所有腐烂橘子一次性入队
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 2) queue.offer(new int[]{i, j});
                else if (grid[i][j] == 1) fresh++;
            }
        }

        if (fresh == 0) return 0;
        int[][] dirs = {{-1,0},{1,0},{0,-1},{0,1}};
        int minutes = 0;

        while (!queue.isEmpty() && fresh > 0) {
            int size = queue.size();
            for (int k = 0; k < size; k++) {
                int[] cur = queue.poll();
                for (int[] d : dirs) {
                    int ni = cur[0] + d[0], nj = cur[1] + d[1];
                    if (ni >= 0 && ni < m && nj >= 0 && nj < n && grid[ni][nj] == 1) {
                        grid[ni][nj] = 2;
                        fresh--;
                        queue.offer(new int[]{ni, nj});
                    }
                }
            }
            minutes++;
        }
        return fresh == 0 ? minutes : -1;
    }
}

例题：LeetCode 542. 01 矩阵

🧊 LeetCode 542 思路+代码

逆向思考：求每个 1 到最近 0 的距离 = 把所有 0 当源点，多源 BFS 一次扩散。

LC542.javajava

class Solution {
    public int[][] updateMatrix(int[][] mat) {
        int m = mat.length, n = mat[0].length;
        int[][] dist = new int[m][n];
        Deque<int[]> queue = new ArrayDeque<>();

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (mat[i][j] == 0) queue.offer(new int[]{i, j});
                else dist[i][j] = -1;     // 用 -1 标记未访问
            }
        }

        int[][] dirs = {{-1,0},{1,0},{0,-1},{0,1}};
        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            for (int[] d : dirs) {
                int ni = cur[0] + d[0], nj = cur[1] + d[1];
                if (ni >= 0 && ni < m && nj >= 0 && nj < n && dist[ni][nj] == -1) {
                    dist[ni][nj] = dist[cur[0]][cur[1]] + 1;
                    queue.offer(new int[]{ni, nj});
                }
            }
        }
        return dist;
    }
}

01-BFS（Zero-One BFS）

适用场景

边权只有 0 和 1 两种值的最短路径问题。Dijkstra 可以做，但 $O((V+E) \log V)$ 略慢；01-BFS 可以做到 $O(V + E)$ 。

核心思想

普通 BFS 用队列，01-BFS 用双端队列：

走权 0 边：邻居加到队头 addFirst（不增加距离，优先处理）
走权 1 边：邻居加到队尾 addLast（增加 1 距离，正常排队）

这样可以保证：双端队列中元素的距离值始终单调不减——和 Dijkstra 的优先队列性质等价，但不需要堆。

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

题意

网格中每个格子有一个箭头方向（1 右、2 左、3 下、4 上）。从 (0,0) 到 (m-1,n-1)，沿箭头方向走代价 0，逆箭头走代价 1，求最小代价。

🎯 LeetCode 1368 完整代码

LC1368.javajava

class Solution {
    public int minCost(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[][] dist = new int[m][n];
        for (int[] row : dist) Arrays.fill(row, Integer.MAX_VALUE);
        dist[0][0] = 0;

        // 方向编号 1234 对应 dirs[1..4]
        int[][] dirs = {{0,0}, {0,1}, {0,-1}, {1,0}, {-1,0}};

        Deque<int[]> deque = new ArrayDeque<>();
        deque.offerFirst(new int[]{0, 0});

        while (!deque.isEmpty()) {
            int[] cur = deque.pollFirst();
            int x = cur[0], y = cur[1];
            for (int k = 1; k <= 4; k++) {
                int nx = x + dirs[k][0], ny = y + dirs[k][1];
                if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue;
                int cost = (grid[x][y] == k) ? 0 : 1;
                int nd = dist[x][y] + cost;
                if (nd < dist[nx][ny]) {
                    dist[nx][ny] = nd;
                    if (cost == 0) deque.offerFirst(new int[]{nx, ny}); // ⭐
                    else deque.offerLast(new int[]{nx, ny});             // ⭐
                }
            }
        }
        return dist[m-1][n-1];
    }
}

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

🧱 LeetCode 2290 思路+代码

思路：空格走代价 0，障碍走代价 1 → 完美匹配 01-BFS。

LC2290.javajava

class Solution {
    public int minimumObstacles(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[][] dist = new int[m][n];
        for (int[] row : dist) Arrays.fill(row, Integer.MAX_VALUE);
        dist[0][0] = 0;

        int[][] dirs = {{-1,0},{1,0},{0,-1},{0,1}};
        Deque<int[]> dq = new ArrayDeque<>();
        dq.offerFirst(new int[]{0, 0});

        while (!dq.isEmpty()) {
            int[] cur = dq.pollFirst();
            int x = cur[0], y = cur[1];
            if (x == m - 1 && y == n - 1) return dist[x][y];
            for (int[] d : dirs) {
                int nx = x + d[0], ny = y + d[1];
                if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue;
                int nd = dist[x][y] + grid[nx][ny];
                if (nd < dist[nx][ny]) {
                    dist[nx][ny] = nd;
                    if (grid[nx][ny] == 0) dq.offerFirst(new int[]{nx, ny});
                    else dq.offerLast(new int[]{nx, ny});
                }
            }
        }
        return dist[m-1][n-1];
    }
}

易错点：dist 必须比较再更新

01-BFS 中同一个节点可能被多次入队（先以较大距离入，后被更短路径"覆盖"）。所以每次出队要再判断一次当前的 dist 是否就是最优值，否则跳过——或者像上面这样，在入队前比较 dist。

优先 BFS（与堆结合）

核心区别

普通 BFS 使用的是 FIFO 队列，谁先入队谁先出队，因此它天然按照“层数”扩散。

优先 BFS 则把普通队列换成了 优先级队列 / 堆，每次都取当前优先级最高的节点进行扩展。

简单说：

text

普通 BFS：按入队顺序扩展
优先 BFS：按优先级扩展

核心技巧

队列换成堆
普通 BFS：
cpp
```
queue<Node> q;
```
优先 BFS：
cpp
```
priority_queue<Node> heap;
```
如果每次要取最小值，一般使用小根堆。
BFS 框架不变
优先 BFS 仍然保留 BFS 的基本流程：
text
```
取出一个点
枚举它的上下左右 / 相邻节点
没访问过就加入容器
```
区别只是容器从 queue 换成了 priority_queue。

优先级怎么定？
由题目决定。
比如：

text

最短路问题：距离越小，优先级越高
接雨水 II：边界高度越低，优先级越高
最小代价问题：总代价越小，优先级越高

本质理解
text
```
优先 BFS = BFS 扩展框架 + 堆控制扩展顺序
```
它经常和 Dijkstra 很像，因为二者都在做：
text
```
每次从当前最优状态继续扩展
```

例题：Leetcode 接雨水 II

木桶效应

二维接雨水的关键是：水能不能存住，取决于当前边界里最低的那块板。

所以我们不能随便扩展，而是必须每次从当前最低边界开始向内扩展。

思路流程

先把矩阵最外圈全部加入小根堆
最外圈无法接水，因为水会从边界流出去
每次弹出当前最低的边界
用这个边界去检查上下左右四个格子
如果邻居比当前水线低，就说明它可以接水
邻居入堆时，它的新高度要变成：
cpp
```
max(heightMap[nx][ny], waterLine)
```

为什么是 `max(height, waterLine)`？

假设当前最低边界高度是 w，邻居原本高度是 h。

如果：

text

h < w

说明这个位置可以接水：

text

接水量 = w - h

但是它被水填平以后，对后面的格子来说，它已经不是高度 h 了，而是高度 w 的“新边界”。

所以入堆高度是：

cpp

max(h, w)

也就是：

text

新边界高度 = max(自身高度, 当前水线高度)

通用模板

cpp

while (!heap.empty()) {
    auto [w, x, y] = heap.top();
    heap.pop();

    for (四个方向) {
        int nx = x + dx;
        int ny = y + dy;

        if (越界 || 已访问) continue;

        visited[nx][ny] = true;

        int h = heightMap[nx][ny];

        if (h < w) {
            ans += w - h;
        }

        heap.push({max(h, w), nx, ny});
    }
}

总结

优先 BFS 就是用堆控制扩展顺序的 BFS。普通 BFS 按层扩展，优先 BFS 按“当前最优状态”扩展。

双向 BFS（Bidirectional BFS）

动机

朴素 BFS 的搜索空间是 $O(b^d)$ （分支因子 $b$ ，深度 $d$ ）。从两端同时搜，每边只需要搜深度 $d/2$ ，总规模降为 $O(2 \cdot b^{d/2})$ —— 指数级提速。

核心技巧

维护两个集合 beginSet 和 endSet，分别存当前层的节点
每轮总是扩展规模较小的那个集合（这是关键优化）
扩展时如果触碰到对方集合 → 找到了，返回当前层数
用 visited 集合去重（双向都要标）

例题：LeetCode 127. 单词接龙（双向版）

同样是 LC127，朴素 BFS 处理大数据集会超时——双向 BFS 才是面试官期待的标准答案。

🚀 LeetCode 127 双向 BFS 完整代码

LC127_Bidirectional.javajava

class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        Set<String> dict = new HashSet<>(wordList);
        if (!dict.contains(endWord)) return 0;

        Set<String> beginSet = new HashSet<>();
        Set<String> endSet = new HashSet<>();
        Set<String> visited = new HashSet<>();
        beginSet.add(beginWord);
        endSet.add(endWord);

        int level = 1;
        while (!beginSet.isEmpty() && !endSet.isEmpty()) {
            // ⭐ 每轮选小的一边扩展
            if (beginSet.size() > endSet.size()) {
                Set<String> tmp = beginSet; beginSet = endSet; endSet = tmp;
            }

            Set<String> nextLevel = new HashSet<>();
            for (String word : beginSet) {
                char[] chars = word.toCharArray();
                for (int i = 0; i < chars.length; i++) {
                    char origin = chars[i];
                    for (char c = 'a'; c <= 'z'; c++) {
                        if (c == origin) continue;
                        chars[i] = c;
                        String next = new String(chars);
                        if (endSet.contains(next)) return level + 1;  // ⭐ 相遇！
                        if (dict.contains(next) && !visited.contains(next)) {
                            nextLevel.add(next);
                            visited.add(next);
                        }
                    }
                    chars[i] = origin;
                }
            }
            beginSet = nextLevel;
            level++;
        }
        return 0;
    }
}

例题：LeetCode 752. 打开转盘锁

🔒 LeetCode 752 思路

思路：每个 4 位密码是一个状态节点，相邻状态相差一位（每位 ±1，共 8 种邻居）。从 "0000" 到 target，避开 deadends。状态空间 $10^4$ 不大但双向 BFS 仍然能显著加速。

实现模板与 LC127 完全一致，只把"换字母"换成"转拨号"即可。

什么时候不要用双向 BFS？

状态空间小（ $< 10^4$ ）：朴素 BFS 已经够快
终点未知或终点是"任意满足条件的状态"（无法从终点反向扩展）
边权不一致（双向 BFS 假设搜索代价对称）

状态：(x, y, keysBitmask)。同一坐标但持钥匙不同算不同状态。

LC864.javajava

class Solution {
    public int shortestPathAllKeys(String[] grid) {
        int m = grid.length, n = grid[0].length();
        int sx = 0, sy = 0, allKeys = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                char c = grid[i].charAt(j);
                if (c == '@') { sx = i; sy = j; }
                else if (c >= 'a' && c <= 'f') allKeys |= (1 << (c - 'a'));
            }
        }

        // 状态: (x << 16) | (y << 8) | keys
        Deque<int[]> queue = new ArrayDeque<>();
        Set<Integer> visited = new HashSet<>();
        queue.offer(new int[]{sx, sy, 0});
        visited.add((sx << 16) | (sy << 8));

        int[][] dirs = {{-1,0},{1,0},{0,-1},{0,1}};
        int step = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int k = 0; k < size; k++) {
                int[] cur = queue.poll();
                int x = cur[0], y = cur[1], keys = cur[2];
                if (keys == allKeys) return step;
                for (int[] d : dirs) {
                    int nx = x + d[0], ny = y + d[1];
                    if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue;
                    char c = grid[nx].charAt(ny);
                    if (c == '#') continue;
                    int nKeys = keys;
                    if (c >= 'a' && c <= 'f') nKeys |= (1 << (c - 'a'));
                    if (c >= 'A' && c <= 'F' && (keys & (1 << (c - 'A'))) == 0) continue;
                    int state = (nx << 16) | (ny << 8) | nKeys;
                    if (visited.add(state)) queue.offer(new int[]{nx, ny, nKeys});
                }
            }
            step++;
        }
        return -1;
    }
}

4. 启发式剪枝（A* 的雏形）

为每个状态估计一个到目标的下界 h，在队列中优先扩展 dist + h 较小者。这就是 A* 算法。BFS 是 h ≡ 0 的特例。

一句话总结剪枝思路

少入队、晚出队——能不入队的状态绝不入队，能延后处理的状态延后处理。

应用一：无向图连通分量

题目：LeetCode 323（会员）

求无向图的连通分量个数。

思路：遍历所有顶点，遇到未访问的就 BFS 一次染色，BFS 次数即连通分量数。

BFS_Components.javajava

class Solution {
    public int countComponents(int n, int[][] edges) {
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) graph.add(new ArrayList<>());
        for (int[] e : edges) {
            graph.get(e[0]).add(e[1]);
            graph.get(e[1]).add(e[0]);
        }
        boolean[] visited = new boolean[n];
        int components = 0;
        Deque<Integer> queue = new ArrayDeque<>();

        for (int i = 0; i < n; i++) {
            if (visited[i]) continue;
            queue.offer(i);
            visited[i] = true;
            while (!queue.isEmpty()) {
                int cur = queue.poll();
                for (int next : graph.get(cur)) {
                    if (!visited[next]) {
                        visited[next] = true;
                        queue.offer(next);
                    }
                }
            }
            components++;     // ⭐ 每发起一次 BFS，分量数 +1
        }
        return components;
    }
}

另一种解法

连通分量也可以用并查集做（每条边合并两端点，最后剩余集合数即答案），代码更短、常数更小。详见文末推荐阅读区。

应用二：判环问题

题目：LeetCode 684. 冗余连接

给一棵树多加了一条边变成图，找出这条多余的边。

思路：对每条新边 (u, v)，加入前先 BFS 查询 u → v 是否已经连通。已连通 ⇒ 该边形成环。

LC684_BFS.javajava

class Solution {
    public int[] findRedundantConnection(int[][] edges) {
        int n = edges.length;
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i <= n; i++) graph.add(new ArrayList<>());

        for (int[] edge : edges) {
            int u = edge[0], v = edge[1];
            if (isConnected(graph, u, v, n)) return edge;
            graph.get(u).add(v);
            graph.get(v).add(u);
        }
        return null;
    }

    private boolean isConnected(List<List<Integer>> graph, int u, int v, int n) {
        boolean[] visited = new boolean[n + 1];
        Deque<Integer> queue = new ArrayDeque<>();
        queue.offer(u);
        visited[u] = true;
        while (!queue.isEmpty()) {
            int cur = queue.poll();
            if (cur == v) return true;
            for (int next : graph.get(cur)) {
                if (!visited[next]) {
                    visited[next] = true;
                    queue.offer(next);
                }
            }
        }
        return false;
    }
}

判环：BFS 不是最优

无向图判环：并查集是最优解（ $O(\alpha(n))$ ）。
有向图判环：用拓扑排序——Kahn 算法（BFS）或 Tarjan 算法（DFS），都是 $O(V + E)$ 。

暴力 BFS/DFS 判环只是基础解法，面试遇到优先用并查集或拓扑排序。

总结

🎀 BFS 全景速记

变种	关键改动	典型用途
朴素 BFS	队列 + visited	遍历、连通性
按层 BFS	每轮记 `size`	层序遍历、最短转换次数
多源 BFS	所有源点同时入队	网格距离扩散
01-BFS	双端队列，0 头 1 尾	边权 ∈ {0,1} 的最短路
双向 BFS	两端同时扩展，扩小集合	状态空间巨大、终点已知

BFS 是最朴素的图算法，也是最深刻的图算法——拓扑排序、最小生成树、最短路径的种子都埋在它的队列里。

图论-广度优先遍历及其拓展

评论区