BFS算法的学习
一. 介绍
广度优先搜索
二. 模板
距离版：用于获取起点到达每个节点的最小距离
/** @description bfs搜索其他点到某个点的最短路径* @param: p* @param: start* @returns int* @author yamu* @date 2025/5/8 15:23*/public int[] bfs(List<Integer>[] p, int start) {int n = p.length;int[] dist = new int[n];Arrays.fill(dist, -1);//表示不可达Deque<Integer> deque = new ArrayDeque<>();dist[start] = 0;//起点deque.add(start);while (!deque.isEmpty()) {int cur = deque.poll();for (int sub_p : p[cur]) {if (dist[sub_p] == -1) {dist[sub_p] = dist[cur] + 1;deque.add(sub_p);}}}return dist;}
层级版：用于按层搜索
/** @description bfs按层搜索 * @param: p* @param: start* @returns void* @author yamu* @date 2025/5/8 15:31*/public void bfs(List<Integer>[] p, int start) {int n = p.length;boolean[] vis = new boolean[n];//记录当前节点是否访问过Deque<Integer> deque = new ArrayDeque<>();deque.add(start);vis[start] = true;while (!deque.isEmpty()) {int size = deque.size();//本层的节点数for (int i = 0; i < size; i++) {int cur = deque.poll();//遍历当前节点下的节点for (int sub_p : p[cur]) {//访问过了if (vis[sub_p]) {continue;}deque.add(sub_p);vis[sub_p] = true;}}}}
三. 题单
转自灵神题单
- 3243. 新增道路查询后的最短距离 I - 力扣（LeetCode）
- 1311. 获取你好友已观看的视频 - 力扣（LeetCode）
- 1129. 颜色交替的最短路径 - 力扣（LeetCode）
- 1298. 你能从盒子里获得的最大糖果数 - 力扣（LeetCode）
- 2039. 网络空闲的时刻 - 力扣（LeetCode）
- 2608. 图中的最短环 - 力扣（LeetCode）
- 815. 公交路线 - 力扣（LeetCode）
3243 好题，bfs统计到达每个点的最短距离；由于单向道路[u -> v]都是满足 v > u，即结果具有递增性（无后效性），可以用dp只bfs
v及v相关的所有点
1311 指定层级level进行bfs
1129 好题，带状态的bfs，需要遍历相反状态的邻接表
1298 暴力 bfs + 判断一下是否访问过
2039 距离模板题
2608 距离模板题
815 好题，多起点多终点找最短路径