Acwing847 图中点的层次（bfs）

本文主要是介绍Acwing847 图中点的层次（bfs），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

这道题用的是bfs，一开始用了dfs搜出了答案为4

题目

给定一个 n个点 m 条边的有向图，图中可能存在重边和自环。

所有边的长度都是 1，点的编号为 1∼n。

请你求出 1 号点到 n 号点的最短距离，如果从 1 号点无法走到 n 号点，输出 −1。

输入格式

第一行包含两个整数 n 和 m。

接下来 m 行，每行包含两个整数 a 和 b，表示存在一条从 a 走到 b 的长度为 1 的边。

输出格式

输出一个整数，表示 1 号点到 n号点的最短距离。

数据范围

1≤n,m≤10

输入样例：

4 5
1 2
2 3
3 4
1 3
1 4

输出样例：

1

解析与代码

bfs的模版思路

1. 使用队列保存待访问的节点。

2. 初始化距离数组（d 数组）为 -1，表示节点未被访问。

3. 将起始节点放入队列，并设置距离为 0。

4. 队列非空时，循环执行以下步骤：

   • 弹出队首节点。
   • 遍历该节点的相邻节点。
   • 如果相邻节点未被访问，更新距离，并将相邻节点入队。

5. 返回目标节点的距离。

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;public class Main {static int n, m, idx, N = 100010, ans = Integer.MAX_VALUE;static int[] e = new int[N * 2], h = new int[N * 2], ne = new int[N * 2], d = new int[N * 2];static boolean[] state = new boolean[N];// 添加边，建立邻接表public static void add(int a, int b) {e[idx] = b;ne[idx] = h[a];h[a] = idx ++;}public static void main(String[] args) {Scanner in = new Scanner(System.in);n = in.nextInt();m = in.nextInt();Arrays.fill(h, -1);// 构建图的邻接表for (int i = 0; i < m; i++) {int a = in.nextInt();int b = in.nextInt();add(a, b);}System.out.println(bfs());}public static int bfs() {Arrays.fill(d, -1);Queue<Integer> q = new LinkedList<>();d[1] = 0;q.offer(1);while (!q.isEmpty()) {int t = q.poll();// 遍历与当前节点 t 相邻的节点for (int i = h[t]; i != -1; i = ne[i]) {int j = e[i];if (d[j] != -1) continue; // 如果节点已经访问过，跳过d[j] = d[t] + 1; // 更新节点 j 的距离q.offer(j); // 将节点 j 入队}}return d[n]; // 返回目标节点 n 的距离}
}

这篇关于Acwing847 图中点的层次（bfs）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---