有向图,点与点之间的关系只用存储一遍。
依然采用邻接表存储图,从起点开始将每个点能走到的点存入队列,然后再 BFS 搜索一遍即可。
数组模拟链表,队列
import java.util.*;
import java.io.BufferedInputStream;
public class Main {
public static int N = 100010, n, index;
/**
* 链表数组,用来存储树中的点在数组模拟链表中的下标
*/
public static int[] head = new int[N];
/**
* 数组模拟链表,存储树中各点
*/
public static int[] e = new int[N];
/**
* 存储树中各点之间的连接关系,由于存储的是有向图,所以两点之间关系只用存储一遍
*/
public static int[] next = new int[N];
/**
* 数组模拟队列,存储当前点能访问到的点
*/
public static int[] queue = new int[N];
/**
* 起点到每个点的最短距离
*/
public static int[] distance = new int[N];
/**
* 每个点是否被搜索过的标记
*/
public static boolean[] state = new boolean[N];
/**
* 将点与点之间的关系存入链表数组
*/
public static void add(int a, int b) {
e[index] = b;
next[index] = head[a];
head[a] = index ++;
}
/**
* 广度优先搜索
*/
public static void bfs(int u) {
// 起点到起点的距离为 0
distance[1] = 0;
// 将当前点入队列
int hh = 0, tt = -1;
queue[++ tt] = u;
// 如果队列不空
while (hh <= tt) {
// 将队头元素弹出,状态置为已搜索
Integer idx = queue[hh ++];
state[idx] = true;
// 从链表中取出与之相连的点
for (int i = head[idx]; i != -1; i = next[i]) {
int j = e[i];
// 如果连接点还未搜索过
if (!state[j]) {
// 比较连接点已存储的起点距离,与当前点再走到连接点的距离谁更小
distance[j] = Math.min(distance[idx] + 1, distance[j]);
// 如果遍历到终点,则结束
if (j == n) return;
// 否则将连接点加入队列
queue[++ tt] = j;
}
}
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(new BufferedInputStream(System.in));
n = sc.nextInt();
int m = sc.nextInt();
// 将所有点的搜索状态置为 false,距起点距离置为 N 默认最大
Arrays.fill(state, false);
Arrays.fill(distance, N);
Arrays.fill(head, -1);
while (m -- > 0) {
// 由于是有向图,所以点与点的关系只用存储一遍
add(sc.nextInt(), sc.nextInt());
}
// 从起点开始 BFS
bfs(1);
// 如果终点存储的起点距离为 N,说明无法走通,输出 -1,否则输出答案
System.out.println(distance[n] == N ? -1 : distance[n]);
sc.close();
}
}
Java Collection Queue,List
import java.util.*;
import java.io.BufferedInputStream;
public class Main {
public static int N = 100010, n;
/**
* 链表数组,用来存储树中的点,以及点与点的指向关系
*/
public static List<Integer>[] head = new ArrayList[N];
/**
* 队列,存储当前点能访问到的点
*/
public static Queue<Integer> queue = new LinkedList<>();
/**
* 起点到每个点的最短距离
*/
public static int[] distance = new int[N];
/**
* 每个点是否被搜索过的标记
*/
public static boolean[] state = new boolean[N];
/**
* 将点与点之间的关系存入链表数组
*/
public static void add(int a, int b) {
if (head[a] == null) {
List<Integer> list = new ArrayList<>();
list.add(b);
head[a] = list;
} else {
head[a].add(b);
}
}
/**
* 广度优先搜索
*/
public static void bfs(int u) {
// 起点到起点的距离为 0
distance[1] = 0;
// 将当前点入队列
queue.add(u);
// 如果队列不空
while (!queue.isEmpty()) {
// 将队头元素弹出,状态置为已搜索
Integer idx = queue.poll();
state[idx] = true;
// 从链表中取出与之相连的点
List<Integer> list = head[idx];
if (list != null) {
for (Integer i : list) {
// 如果连接点还未搜索过
if (!state[i]) {
// 比较连接点已存储的起点距离,与当前点再走到连接点的距离谁更小
distance[i] = Math.min(distance[idx] + 1, distance[i]);
// 如果遍历到终点,则结束
if (i == n) return;
// 否则将连接点加入队列
queue.add(i);
}
}
}
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(new BufferedInputStream(System.in));
n = sc.nextInt();
int m = sc.nextInt();
// 将所有点的搜索状态置为 false,距起点距离置为 N 默认最大
Arrays.fill(state, false);
Arrays.fill(distance, N);
while (m -- > 0) {
// 由于是有向图,所以点与点的关系只用存储一遍
add(sc.nextInt(), sc.nextInt());
}
// 从起点开始 BFS
bfs(1);
// 如果终点存储的起点距离为 N,说明无法走通,输出 -1,否则输出答案
System.out.println(distance[n] == N ? -1 : distance[n]);
sc.close();
}
}