图中点的层次
给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环
所有边的长度都是 1，点的编号为 1 ∼ n
请你求出 1 号点到 n 号点的最短距离，如果从 1 号点无法走到 n 号点，输出 −1
输入格式
- 第一行包含两个整数
n 和 m
- 接下来
m 行，每行包含两个整数 a 和 b，表示存在一条从 a 走到 b 的长度为 1 的边
输出格式
- 输出一个整数，表示
1 号点到 n 号点的最短距离
数据范围
输入样例
1
2
3
4
5
6
|
4 5
1 2
2 3
3 4
1 3
1 4
|
输出样例
分析
- 邻接表存储：
h[N]：存储每个节点的邻接链表的头节点（初始化为 -1）e[N]：存储邻接表中的边的目标节点ne[N]：存储邻接表中链表的下一个节点的索引idx：记录当前边的编号
add(a, b)：将一条从节点 a 到节点 b 的边加入邻接表中bfs()：
- 初始化
d 数组为 -1，表示所有节点初始时不可达
- 从节点
1 开始进行 BFS，记录每个节点的最短路径
- 如果节点
n 被访问过，则返回 d[n]；否则返回 -1
时间复杂度
BFS 只会遍历每个节点和每条边一次，其中 n 是节点数，m 是边数
时间复杂度为 O(n + m)
空间复杂度
- 存储图的邻接表需要
O(n + m) 的空间
- 存储队列和距离数组需要
O(n) 的空间
空间复杂度为 O(n + m)
C++代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
|
#include <cstring>
#include <iostream>
const int N = 100010; // 节点和边的最大数量
int h[N], e[N], ne[N], idx; // 邻接表存储
int q[N]; // 队列
int d[N]; // 存储最短路径
int n, m; // 节点数和边数
// 添加一条边到邻接表
void add(int a, int b)
{
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}
// BFS 求最短路径
int bfs()
{
int hh = 0, tt = 0;
q[0] = 1; // 起始节点 1
std::memset(d, -1, sizeof(d)); // 初始化距离数组为 -1
d[1] = 0; // 起点到起点的距离为 0
while (hh <= tt) // 队列不为空
{
int t = q[hh++]; // 出队一个节点
for (int i = h[t]; i != -1; i = ne[i]) // 遍历该节点的所有邻接节点
{
int j = e[i]; // 邻接节点 j
if (d[j] == -1) // 如果节点 j 尚未访问
{
d[j] = d[t] + 1; // 更新节点 j 的距离
q[++tt] = j; // 将节点 j 加入队列
}
}
}
return d[n]; // 返回从 1 到 n 的最短路径长度
}
int main()
{
std::cin >> n >> m; // 输入节点数和边数
std::memset(h, -1, sizeof(h)); // 初始化邻接表
for (int i = 0; i < m; ++i)
{
int a, b;
std::cin >> a >> b; // 输入每条边
add(a, b); // 将边加入邻接表
}
std::cout << bfs() << '\n'; // 输出从 1 到 n 的最短距离
return 0;
}
|
