BFS（广度优先搜索）及经典变种 + Java 实现

目录一、BFS广度优先搜索及经典变种 Java 实现1. 基础 BFS 原理1.1 基础 BFS邻接表实现 无向图1.2 BFS 变种 1带路径记录的 BFS无权最短路径1.3 BFS 变种 2多源 BFS1.4 BFS 变种 3双向 BFS一、BFS广度优先搜索及经典变种 Java 实现1. 基础 BFS 原理核心思想按层遍历图 / 树使用队列实现先访问当前节点所有邻接节点再遍历下一层。适用无权图最短路径、迷宫遍历、层次遍历、连通块统计特点无权图中首次到达目标节点的路径就是最短路径1.1 基础 BFS邻接表实现 无向图import java.util.*; public class BasicBFS { // 邻接表存图 private static ListListInteger 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) { QueueInteger 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 51.2 BFS 变种 1带路径记录的 BFS无权最短路径在基础 BFS 上增加前驱数组回溯得到完整路径。import java.util.*; public class BFS_ShortestPath { private static ListListInteger 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 表示无前驱 QueueInteger 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) { ListInteger 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]; Queueint[] 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 ListListInteger 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; QueueInteger qStart new LinkedList(); QueueInteger qEnd new LinkedList(); SetInteger visStart new HashSet(); SetInteger 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; // 不可达 } }