图的存储、DFS与BFS

考点定位

本课深化 图的存储、DFS与BFS。408作答必须同时给出数据结构表示、算法过程、不变量、复杂度和边界条件。

结构与取舍

邻接矩阵适合稠密图且判边O(1)；邻接表适合稀疏图。DFS使用递归/栈，BFS使用队列并按边数层次扩展。

算法推演

无权图最短路BFS：源点距离0入队；每次出队u，仅对未访问邻点v设置dist[v]=dist[u]+1并入队。

把算法写成“初始化—循环条件—状态更新—终止输出”。若使用递归、队列、堆或并查集，要指出其中保存的状态及何时失效。

正确性不变量

结点第一次入队时得到从源点出发的最短边数，此后不得重复改大。

初始化时不变量成立；一次迭代保持它；循环结束时它与终止条件共同推出答案。这是算法题证明的最短主线。

复杂度与边界

时间复杂度必须按输入规模和存储结构计算，不能只报结论。严格边界：遍历序列可能受邻接点顺序影响，但访问集合和BFS距离不受合法顺序影响。

随课应用

输入n m，随后m行无向边u v（结点0..n-1），最后一行源点s。输出从s到各点的最少边数，不可达输出-1。

先独立计算或编码，再完成单选与多选。代码题从标准输入读取并写到标准输出，不得硬编码样例；数值题需写出中间状态。