这道题用的是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的模版思路
-
使用队列保存待访问的节点。
-
初始化距离数组(
d
数组)为 -1,表示节点未被访问。 -
将起始节点放入队列,并设置距离为 0。
-
队列非空时,循环执行以下步骤:文章来源:https://www.toymoban.com/news/detail-786818.html
- 弹出队首节点。
- 遍历该节点的相邻节点。
- 如果相邻节点未被访问,更新距离,并将相邻节点入队。
-
返回目标节点的距离。文章来源地址https://www.toymoban.com/news/detail-786818.html
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)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!