目录
一、BFS（广度优先搜索）及经典变种 + Java 实现
1. 基础 BFS 原理
1.1 基础 BFS（邻接表实现 无向图）
1.2 BFS 变种 1：带路径记录的 BFS（无权最短路径）
1.3 BFS 变种 2：多源 BFS
1.4 BFS 变种 3：双向 BFS
一、BFS（广度优先搜索）及经典变种 + Java 实现
1. 基础 BFS 原理
核心思想：按层遍历图 / 树，使用队列实现，先访问当前节点所有邻接节点，再遍历下一层。
- 适用：无权图最短路径、迷宫遍历、层次遍历、连通块统计
- 特点：无权图中，首次到达目标节点的路径就是最短路径
1.1 基础 BFS（邻接表实现 无向图）
import java.util.*; public class BasicBFS { // 邻接表存图 private static List<List<Integer>> graph; // 标记是否访问 private static boolean[] visited; public static void main(String[] args) { int n = 6; // 节点数 0~5 initGraph(n); // 从节点 0 开始 BFS bfs(0); } // 初始化图 private static void initGraph(int n) { graph = new ArrayList<>(); for (int i = 0; i < n; i++) { graph.add(new ArrayList<>()); } // 构建边 graph.get(0).add(1); graph.get(0).add(2); graph.get(1).add(0); graph.get(1).add(3); graph.get(2).add(0); graph.get(2).add(4); graph.get(3).add(1); graph.get(3).add(5); graph.get(4).add(2); graph.get(5).add(3); visited = new boolean[n]; } // 基础 BFS public static void bfs(int start) { Queue<Integer> queue = new LinkedList<>(); queue.offer(start); visited[start] = true; while (!queue.isEmpty()) { int cur = queue.poll(); System.out.print(cur + " "); // 遍历所有邻接节点 for (int next : graph.get(cur)) { if (!visited[next]) { visited[next] = true; queue.offer(next); } } } } }输出：0 1 2 3 4 5
1.2 BFS 变种 1：带路径记录的 BFS（无权最短路径）
在基础 BFS 上增加前驱数组，回溯得到完整路径。
import java.util.*; public class BFS_ShortestPath { private static List<List<Integer>> graph; private static int[] pre; // 前驱节点，记录路径 public static void main(String[] args) { int n = 6; initGraph(n); int start = 0; int end = 5; bfsPath(start, n); // 回溯输出路径 printPath(start, end); } private static void initGraph(int n) { graph = new ArrayList<>(); for (int i = 0; i < n; i++) graph.add(new ArrayList<>()); graph.get(0).add(1); graph.get(0).add(2); graph.get(1).add(0); graph.get(1).add(3); graph.get(2).add(0); graph.get(2).add(4); graph.get(3).add(1); graph.get(3).add(5); graph.get(4).add(2); graph.get(5).add(3); } public static void bfsPath(int start, int n) { boolean[] visited = new boolean[n]; pre = new int[n]; Arrays.fill(pre, -1); // -1 表示无前驱 Queue<Integer> q = new LinkedList<>(); q.offer(start); visited[start] = true; while (!q.isEmpty()) { int cur = q.poll(); for (int next : graph.get(cur)) { if (!visited[next]) { visited[next] = true; pre[next] = cur; q.offer(next); } } } } // 回溯打印路径 public static void printPath(int start, int end) { List<Integer> path = new ArrayList<>(); int cur = end; while (cur != -1) { path.add(cur); cur = pre[cur]; } Collections.reverse(path); System.out.println("最短路径：" + path); } }输出：最短路径：[0, 1, 3, 5]
1.3 BFS 变种 2：多源 BFS
场景：多个起点同时向外层扩散（如：多起点迷宫、洪水填充、最近距离）。 原理：初始队列一次性加入所有源点，后续逻辑和普通 BFS 一致。
示例：求每个节点距离最近源点的距离
import java.util.*; public class MultiSourceBFS { public static void main(String[] args) { // 网格：0=空地，1=源点 int[][] grid = { {1, 0, 0}, {0, 0, 0}, {0, 0, 1} }; int[][] dist = multiSourceBFS(grid); // 打印距离矩阵 for (int[] row : dist) { System.out.println(Arrays.toString(row)); } } // 上下左右四个方向 private static final int[][] dirs = {{-1,0},{1,0},{0,-1},{0,1}}; public static int[][] multiSourceBFS(int[][] grid) { int m = grid.length, n = grid[0].length; int[][] dist = new int[m][n]; boolean[][] visited = new boolean[m][n]; Queue<int[]> queue = new LinkedList<>(); // 1. 多源：所有 1 作为起点入队 for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (grid[i][j] == 1) { queue.offer(new int[]{i, j}); visited[i][j] = true; dist[i][j] = 0; } } } // 2. 层序遍历 while (!queue.isEmpty()) { int[] cur = queue.poll(); int x = cur[0], y = cur[1]; for (int[] d : dirs) { int nx = x + d[0]; int ny = y + d[1]; if (nx >= 0 && nx < m && ny >=0 && ny < n && !visited[nx][ny]) { visited[nx][ny] = true; dist[nx][ny] = dist[x][y] + 1; queue.offer(new int[]{nx, ny}); } } } return dist; } }1.4 BFS 变种 3：双向 BFS
场景：起点、终点已知，大幅减少搜索节点（单向 BFS 层数爆炸时优化）。 原理：起点队列、终点队列同时向中间遍历，两边相遇即找到最短路径。
import java.util.*; public class TwoWayBFS { private static List<List<Integer>> graph; public static void main(String[] args) { int n = 6; initGraph(n); int start = 0, end = 5; int res = twoWayBFS(start, end, n); System.out.println("最短路径长度：" + res); } private static void initGraph(int n) { graph = new ArrayList<>(); for (int i = 0; i < n; i++) graph.add(new ArrayList<>()); graph.get(0).add(1); graph.get(0).add(2); graph.get(1).add(0); graph.get(1).add(3); graph.get(2).add(0); graph.get(2).add(4); graph.get(3).add(1); graph.get(3).add(5); graph.get(4).add(2); graph.get(5).add(3); } public static int twoWayBFS(int start, int end, int n) { if (start == end) return 0; Queue<Integer> qStart = new LinkedList<>(); Queue<Integer> qEnd = new LinkedList<>(); Set<Integer> visStart = new HashSet<>(); Set<Integer> visEnd = new HashSet<>(); qStart.offer(start); qEnd.offer(end); visStart.add(start); visEnd.add(end); int step = 0; while (!qStart.isEmpty() && !qEnd.isEmpty()) { step++; // 正向遍历一层 int size = qStart.size(); for (int i = 0; i < size; i++) { int cur = qStart.poll(); for (int next : graph.get(cur)) { if (visEnd.contains(next)) return step; // 相遇 if (!visStart.contains(next)) { visStart.add(next); qStart.offer(next); } } } step++; // 反向遍历一层 size = qEnd.size(); for (int i = 0; i < size; i++) { int cur = qEnd.poll(); for (int next : graph.get(cur)) { if (visStart.contains(next)) return step; // 相遇 if (!visEnd.contains(next)) { visEnd.add(next); qEnd.offer(next); } } } } return -1; // 不可达 } }
