這道題用的是bfs，一開始用了dfs搜出了答案為4

題目

給定一個?n個點?m?條邊的有向圖，圖中可能存在重邊和自環(huán)。

所有邊的長度都是?1，點的編號為?1～n。

請你求出?1?號點到?n?號點的最短距離，如果從?1?號點無法走到?n?號點，輸出??1。

輸入格式

第一行包含兩個整數(shù)?n?和?m。

接下來?m?行，每行包含兩個整數(shù)?a?和?b，表示存在一條從?a?走到?b?的長度為?1?的邊。

輸出格式

輸出一個整數(shù)，表示?1?號點到?n號點的最短距離。

數(shù)據(jù)范圍

1≤n,m≤10

輸入樣例：

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

輸出樣例：

1

解析與代碼

bfs的模版思路

1. 使用隊列保存待訪問的節(jié)點。

2. 初始化距離數(shù)組（d 數(shù)組）為 -1，表示節(jié)點未被訪問。

3. 將起始節(jié)點放入隊列，并設(shè)置距離為 0。

4. 隊列非空時，循環(huán)執(zhí)行以下步驟：

   • 彈出隊首節(jié)點。
   • 遍歷該節(jié)點的相鄰節(jié)點。
   • 如果相鄰節(jié)點未被訪問，更新距離，并將相鄰節(jié)點入隊。

5. 返回目標(biāo)節(jié)點的距離。

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);// 構(gòu)建圖的鄰接表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();// 遍歷與當(dāng)前節(jié)點 t 相鄰的節(jié)點for (int i = h[t]; i != -1; i = ne[i]) {int j = e[i];if (d[j] != -1) continue; // 如果節(jié)點已經(jīng)訪問過，跳過d[j] = d[t] + 1; // 更新節(jié)點 j 的距離q.offer(j); // 將節(jié)點 j 入隊}}return d[n]; // 返回目標(biāo)節(jié)點 n 的距離}
}