考研408数据结构——图的最短路径与最小生成树算法全解

本文系统梳理408数据结构图论核心算法覆盖Dijkstra、Floyd最短路径算法及Prim、Kruskal最小生成树算法结合历年真题出题角度进行深度分析适合计算机专业考研同学参考。目录一、图算法在408考试中的地位二、最短路径算法2.1 Dijkstra算法2.2 Floyd算法2.3 两种最短路径算法对比三、最小生成树算法3.1 Prim算法3.2 Kruskal算法3.3 Prim与Kruskal对比四、算法复杂度汇总对比五、历年真题考查分析六、学习资源推荐一、图算法在408考试中的地位408计算机学科专业基础综合中数据结构约占45分比重而图论相关算法几乎每年必考常出现在选择题和算法大题中。近10年真题中图算法相关题目出现频率如下考点出现年份题型Dijkstra算法2015、2017、2019、2021、2023选择/简答Floyd算法2016、2018、2022选择Prim算法2014、2017、2020、2023选择/填空Kruskal算法2015、2019、2021、2022选择/填空综合应用2020、2023算法设计题可以看出最短路径和最小生成树是高频考点需要深入理解算法原理并能手写出核心代码。二、最短路径算法2.1 Dijkstra算法核心思想贪心策略从源点出发每次选取距离最短的已确定顶点用该顶点更新其余顶点的距离估计值。适用于单源最短路径问题要求图中边权非负。算法步骤初始化将源点距离设为0其余顶点距离设为∞所有顶点标记为未访问从未访问顶点中选取距离最小的顶点u标记为已访问对u的所有邻接顶点v若dist[u] weight(u,v) dist[v]则更新dist[v]重复步骤2-3直到所有顶点均已访问C语言实现#defineMAXVEX100#defineINFINITY65535typedefstruct{intvexs[MAXVEX];// 顶点表intarc[MAXVEX][MAXVEX];// 邻接矩阵intvexNum,arcNum;// 顶点数和边数}MGraph;voidDijkstra(MGraph G,intv0,intdist[],intpath[]){intfinal[MAXVEX];// 标记顶点是否已求得最短路径inti,j,k,min;// 初始化for(i0;iG.vexNum;i){final[i]0;dist[i]G.arc[v0][i];if(dist[i]INFINITY)path[i]v0;elsepath[i]-1;}final[v0]1;dist[v0]0;// 主循环for(i1;iG.vexNum;i){minINFINITY;for(j0;jG.vexNum;j){// 找最小distif(!final[j]dist[j]min){kj;mindist[j];}}final[k]1;// 标记已访问// 更新邻接顶点距离for(j0;jG.vexNum;j){if(!final[j]minG.arc[k][j]dist[j]){dist[j]minG.arc[k][j];path[j]k;}}}}时间复杂度分析使用邻接矩阵存储时时间复杂度为O(V²)若使用邻接表优先队列堆优化可优化至O((VE)logV)。408考试中常考查邻接矩阵版本的手写模拟。2.2 Floyd算法核心思想动态规划思想通过逐步插入中间顶点来更新任意两点间的最短距离。适用于多源最短路径问题可处理负权边但不能有负权回路。状态转移方程D^(k)[i][j] min(D^(k-1)[i][j], D^(k-1)[i][k] D^(k-1)[k][j])其中k为当前允许经过的中间顶点编号。C语言实现voidFloyd(MGraph G,intdist[][MAXVEX],intpath[][MAXVEX]){inti,j,k;// 初始化距离矩阵和路径矩阵for(i0;iG.vexNum;i){for(j0;jG.vexNum;j){dist[i][j]G.arc[i][j];if(i!jdist[i][j]INFINITY)path[i][j]i;elsepath[i][j]-1;}}// 三重循环k为中间顶点for(k0;kG.vexNum;k){for(i0;iG.vexNum;i){for(j0;jG.vexNum;j){if(dist[i][k]dist[k][j]dist[i][j]){dist[i][j]dist[i][k]dist[k][j];path[i][j]path[k][j];}}}}}注意三重循环的嵌套顺序不能颠倒最外层必须是k中间顶点这是Floyd算法正确性的关键。2.3 两种最短路径算法对比对比维度DijkstraFloyd适用场景单源最短路径多源全源最短路径边权限制非负权可处理负权无负权回路时间复杂度O(V²) / O((VE)logV)堆优化O(V³)空间复杂度O(V)O(V²)算法思想贪心动态规划存储结构邻接矩阵/邻接表邻接矩阵408考查频率★★★★★★★★★三、最小生成树算法最小生成树MST的目标在连通图中找到一棵包含所有顶点的生成树使得树上所有边的权值之和最小。3.1 Prim算法核心思想从某一顶点开始逐步扩展生成树。每次从未加入树中的顶点中选取与当前树相连的边权最小的顶点加入。属于加点法。C语言核心逻辑voidPrim(MGraph G,intclosedge[]){intlowcost[MAXVEX];// 记录生成树到各顶点的最小边权intadjvex[MAXVEX];// 记录最小边对应的树中顶点inti,j,k,min;// 从顶点0开始构造最小生成树for(i0;iG.vexNum;i){lowcost[i]G.arc[0][i];adjvex[i]0;}lowcost[0]0;// 顶点0加入生成树for(i1;iG.vexNum;i){// 找lowcost中最小值minINFINITY;for(j0;jG.vexNum;j){if(lowcost[j]!0lowcost[j]min){minlowcost[j];kj;}}// 输出边(adjvex[k], k)printf((%d, %d),adjvex[k],k);lowcost[k]0;// 顶点k加入生成树// 更新lowcostfor(j0;jG.vexNum;j){if(lowcost[j]!0G.arc[k][j]lowcost[j]){lowcost[j]G.arc[k][j];adjvex[j]k;}}}}3.2 Kruskal算法核心思想将所有边按权值从小到大排序依次选取不构成回路的边加入生成树。属于加边法需要借助并查集来判断是否构成回路。C语言核心逻辑typedefstruct{intbegin,end,weight;}Edge;// 并查集查找根节点intFind(intparent[],intf){while(parent[f]0)fparent[f];returnf;}voidKruskal(MGraph G,Edge edges[]){intparent[MAXVEX]{0};inti,n,m;// 按weight排序后依次处理每条边for(i0;iG.arcNum;i){nFind(parent,edges[i].begin);mFind(parent,edges[i].end);if(n!m){// 不在同一集合不构成回路parent[n]m;printf((%d, %d) weight%d\n,edges[i].begin,edges[i].end,edges[i].weight);}}}3.3 Prim与Kruskal对比对比维度PrimKruskal策略加点法加边法适用场景稠密图边多稀疏图边少时间复杂度O(V²)邻接矩阵O(ElogE)边排序辅助结构lowcost数组并查集实现难度中等需实现排序并查集408考查重点手动模拟选点过程手动模拟选边判断回路四、算法复杂度汇总对比算法时间复杂度空间复杂度适用图类型Dijkstra邻接矩阵O(V²)O(V)稠密图Dijkstra堆优化O((VE)logV)O(VE)稀疏图FloydO(V³)O(V²)全源、任意密度Prim邻接矩阵O(V²)O(V)稠密图KruskalO(ElogE)O(E)稀疏图备考提示408考试中常要求考生根据具体图结构手动模拟算法执行过程记录每轮选择结果。建议对每个算法至少手算2-3道不同规模的题目。五、历年真题考查分析根据对近10年408真题的统计图算法出题角度主要包括1. 算法过程模拟题高频给出一张带权图要求按照Dijkstra/Prim/Kruskal的步骤逐步写出执行过程记录每轮选取的顶点和更新后的距离数组。2. 算法性质判断题中频例如Dijkstra能否处理负权边为什么Floyd算法中三重循环顺序能否改变Prim算法和Dijkstra算法的异同点是什么3. 代码填空题中频给出不完整的算法代码要求补全关键逻辑如更新距离、标记访问状态等。4. 算法设计题低频但分值高结合具体应用场景如交通网络、通信网络要求设计算法求最短路径或最小代价并分析复杂度。年份题号考查内容分值202336-37Prim算法过程模拟8分202341最短路径应用设计10分20229-10Floyd算法性质4分202235Kruskal算法模拟8分20217-8Dijkstra执行过程4分202142图综合应用10分六、学习资源推荐图算法是408数据结构中的重点模块建议结合教材严蔚敏《数据结构》、王道考研系列系统学习并通过大量真题练习巩固。对于基础薄弱或需要系统辅导的同学可以参考交大典博的考研计算机专业课程——该机构依托西南交通大学高校资源采用小班教学模式在408全科辅导方面有丰富的教学经验适合备考西南交大及其他计算机院校的考生。