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;
				}
			}
		}
	}

三. 题单

转自灵神题单

1. 3243. 新增道路查询后的最短距离 I - 力扣（LeetCode）
2. 1311. 获取你好友已观看的视频 - 力扣（LeetCode）
3. 1129. 颜色交替的最短路径 - 力扣（LeetCode）
4. 1298. 你能从盒子里获得的最大糖果数 - 力扣（LeetCode）
5. 2039. 网络空闲的时刻 - 力扣（LeetCode）
6. 2608. 图中的最短环 - 力扣（LeetCode）
7. 815. 公交路线 - 力扣（LeetCode）

3243 好题，bfs统计到达每个点的最短距离；由于单向道路[u -> v]都是满足 v > u，即结果具有递增性（无后效性），可以用dp只bfs
v及v相关的所有点
1311 指定层级level进行bfs
1129 好题，带状态的bfs，需要遍历相反状态的邻接表
1298 暴力 bfs + 判断一下是否访问过
2039 距离模板题
2608 距离模板题
815 好题，多起点多终点找最短路径