算法讲解8：搜索之bfs(广度优先）

搜索：穷尽所有的可能找到最优解，或统计和法解的个数

分类：dfs,bfs

特点：有多种优化方式，如减小状态空间，更改搜索顺序，剪枝等

对于bfs，每次都先处理该层图层

例题：

题目描述

小 A 有一棵 n 个结点的树，这些结点依次以 1,2,⋯,n 标号。

小 A 想在这棵树上漫步。具体来说，小 A 会从树上的某个结点出发，每一步可以移动到与当前结点相邻的结点，并且小 A 只会在偶数步（可以是零步）后结束漫步。

现在小 A 想知道，对于树上的每个结点，从这个结点出发开始漫步，经过偶数步能结束漫步的结点有多少个（可以经过重复的节点）。

输入格式

第一行，一个正整数 n。

接下来 n−1 行，每行两个整数 ui​,vi​，表示树上有⼀条连接结点 ui​ 和结点 vi​ 的边。

输出格式

一行，n 个整数。第 i 个整数表示从结点 i 出发开始漫步，能结束漫步的结点数量。

输入输出样例

输入 #1复制

3 1 3 2 3

输出 #1复制

2 2 1

import java.util.*;//一次性等于使用所有util的 //树是二分图（无奇环），任意两点的路径长度奇偶性固定 //需要二分 //- 同层节点（如偶-偶、奇-奇）：层数差为0（偶数）→ 路径长度必为偶数； //- 异层节点（如偶-奇）：层数差为1（奇数）→ 路径长度必为奇数； public class p11962 { static List<List<Integer>> adj;//邻接表 static int[] color; static int cnt0,cnt1;//静态修饰的默认为0 public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); adj = new ArrayList<>();//对邻接表的初始化 for (int i = 0; i <= n; i++) adj.add(new ArrayList<>());//每次循环给外层列表adj添加一个新的空arraylist,整体是邻接表的内层初始化 for (int i = 0; i < n-1; i++) { int u = sc.nextInt(), v = sc.nextInt(); adj.get(u).add(v);//节点u的相邻节点包含v adj.get(v).add(u);//就相当于一切的基础，相当于1棵树，不过两者相互连结需要在后面用 if (color[v] == -1)来保持正常 } color = new int[n+1]; Arrays.fill(color, -1);//将数组中所有的元素都初始化为-1 bfs(1); // 从节点1开始染色 // 输出每个节点的结果 for (int i = 1; i <= n; i++) { System.out.print((color[i] == 0 ? cnt0 : cnt1) + " "); }//color[i]=0说明是偶数分组，该组有几个就输出几个 //color=0 说明当前节点属于“偶层分组”，而偶层分组的所有节点，都能通过偶数步到达当前节点 //color=1 时，输出的是 cnt1 ——因为 color=1 表示当前节点属于“奇层分组”，该分组的所有节点都能通过偶数步到达当前节点， // cnt1 正是这个分组的总节点数。 } static void bfs(int start) {//广度优先搜索 Queue<Integer> q = new LinkedList<>(); q.add(start);//1.队列的作用：维持“待处理节点”顺序，确保先处理父节点、再处理子节点（符合树的层级遍历逻辑）； color[start] = 0; cnt0++; while (!q.isEmpty()) {//队列不为空就持续染色 int u = q.poll();//取出头部，poll是取出并移除 for (int v : adj.get(u)) {//adj.u代表的是与节点u相邻的所有节点，整体上市遍历节点u相邻的所有节点后赋值给v if (color[v] == -1) {//保证只能被染色一次,想想之前输入的时候队adj做的，想象树从上往下找，这行代码就杜绝从下往上的可能 color[v] = color[u] ^ 1; // 0^1=1,1^1=0---v一定与u相邻，这行本质上就是，给v和u相反的颜色 if (color[v] == 0) cnt0++;//计数 else cnt1++; q.add(v);//这个队列在for循环的时候一直加 } } } } }