最短路径
Coddy 图：数据结构系列 #9 课程的第 12 课，共 14 课。
从 start 到 end 最少需要经过多少条边？在无权图中（每条边的代价都相同），答案正是 BFS 计算出的结果。因为 BFS 会按照与起点距离递增的顺序访问顶点，所以第一次到达 end 时，经过的就是一条最短路径。
诀窍是将每个顶点和当前距离一起加入队列。先加入 (start, 0)。每当你从距离为 d 的顶点发现一个新邻居 v 时，就将 (v, d + 1) 加入队列。当 v == end 时，返回 d + 1。
有两种边界情况。如果 start == end，答案是 0。如果 BFS 结束时仍未到达 end，那么这两个顶点位于不同的连通分量中，答案是 -1。
挑战
简单编写一个函数 shortestPath，它接收一个二维 int 数组 adjacency、一个 int start 和一个 int end，并返回从 start 到 end 的最短距离（边数）。
- 如果
start == end，返回0。 - 如果从
start无法到达end，返回-1。 - 否则，返回它们之间的最少边数。
你必须使用 Graph 类（已在 graph 中提供），不要使用语言内置类型（映射、集合）来表示邻接关系。算法的辅助数据（已访问集合、队列）可以使用标准库类型。
亲手试试
#include <stdio.h>
#include "solution.h"
int main() {
int n, m, start, end;
if (scanf("%d %d %d %d", &n, &m, &start, &end) != 4) return 0;
int adjacency[1024][2];
for (int i = 0; i < m; i++) scanf("%d %d", &adjacency[i][0], &adjacency[i][1]);
printf("%d\n", shortestPath(adjacency, m, start, end));
return 0;
}
图：数据结构系列 #9中的所有课
自己练习： C 在线编译器