图的应用是 408 数据结构部分的大题高频考点最短路径、最小生成树、拓扑排序几乎每年必考一个。一、最短路径1. Dijkstra 算法Dijkstra 算法求单源最短路径适用于边权非负的图。核心思想每次从未访问的节点中选距离起点最短的用它更新邻居的距离。publicclassDijkstra{/** * param graph 邻接矩阵graph[i][j]0 表示无边 * param start 起点 * return dist[] 到各点的最短距离 */publicstaticint[]dijkstra(int[][]graph,intstart){intngraph.length;int[]distnewint[n];boolean[]visitednewboolean[n];// 初始化距离Arrays.fill(dist,Integer.MAX_VALUE);dist[start]0;for(inti0;in-1;i){// 1. 选未访问的距离最小的顶点intu-1;intminDistInteger.MAX_VALUE;for(intj0;jn;j){if(!visited[j]dist[j]minDist){minDistdist[j];uj;}}if(u-1)break;// 剩余的不可达visited[u]true;// 2. 用 u 更新邻居的距离for(intv0;vn;v){if(!visited[v]graph[u][v]!0dist[u]graph[u][v]dist[v]){dist[v]dist[u]graph[u][v];}}}returndist;}}时间复杂度O(n²)可以用优先队列优化到 O((ne) log n)2. Floyd 算法Floyd 算法求所有点对之间的最短路径可以处理负权边但不能有负环。publicclassFloyd{/** * param graph 邻接矩阵graph[i][j]INF 表示无边 * return dist[][] 任意两点间最短距离 */publicstaticint[][]floyd(int[][]graph){intngraph.length;int[][]distnewint[n][n];// 初始化for(inti0;in;i){System.arraycopy(graph[i],0,dist[i],0,n);}// 三重循环for(intk0;kn;k){// 中间点for(inti0;in;i){// 起点for(intj0;jn;j){// 终点if(dist[i][k]!Integer.MAX_VALUEdist[k][j]!Integer.MAX_VALUEdist[i][k]dist[k][j]dist[i][j]){dist[i][j]dist[i][k]dist[k][j];}}}}returndist;}}时间复杂度O(n³)3. Dijkstra vs Floyd对比DijkstraFloyd适用单源最短路径所有点对最短路径边权不能有负权不能有负环时间复杂度O(n²)O(n³)空间复杂度O(n)O(n²)二、最小生成树1. Prim 算法Prim 算法从顶点出发每次选权值最小的边加入。publicclassPrim{/** * param graph 邻接矩阵 * return 最小总权值 */publicstaticintprim(int[][]graph){intngraph.length;int[]lowCostnewint[n];// 到各顶点的最小权值boolean[]visitednewboolean[n];inttotal0;// 从顶点 0 开始visited[0]true;for(inti1;in;i){lowCost[i]graph[0][i];}for(inti1;in;i){// 找权值最小的未访问顶点intminInteger.MAX_VALUE;intminIdx-1;for(intj0;jn;j){if(!visited[j]lowCost[j]minlowCost[j]!0){minlowCost[j];minIdxj;}}if(minIdx-1)break;// 不连通visited[minIdx]true;totalmin;// 更新 lowCostfor(intj0;jn;j){if(!visited[j]graph[minIdx][j]!0graph[minIdx][j]lowCost[j]){lowCost[j]graph[minIdx][j];}}}returntotal;}}适合稠密图时间复杂度 O(n²)。2. Kruskal 算法Kruskal 算法从边出发每次选权值最小的边不形成环就加入。publicclassKruskal{staticclassEdgeimplementsComparableEdge{intu,v,weight;Edge(intu,intv,intweight){this.uu;this.vv;this.weightweight;}OverridepublicintcompareTo(Edgeo){returnthis.weight-o.weight;}}staticclassUnionFind{int[]parent;UnionFind(intn){parentnewint[n];for(inti0;in;i)parent[i]i;}intfind(intx){if(parent[x]!x){parent[x]find(parent[x]);}returnparent[x];}booleanunion(intx,inty){intrxfind(x);intryfind(y);if(rxry)returnfalse;parent[rx]ry;returntrue;}}publicstaticintkruskal(ListEdgeedges,intn){Collections.sort(edges);// 按权值排序UnionFindufnewUnionFind(n);inttotal0;intedgeCount0;for(Edgee:edges){if(uf.union(e.u,e.v)){totale.weight;edgeCount;if(edgeCountn-1)break;}}returnedgeCountn-1?total:-1;// -1 表示不连通}}适合稀疏图时间复杂度 O(e log e)。3. Prim vs Kruskal对比PrimKruskal策略选顶点选边数据结构邻接矩阵边集 并查集时间复杂度O(n²)O(e log e)适合稠密图稀疏图三、拓扑排序拓扑排序是有向无环图DAG的顶点线性排序AOV 网中活动执行的先后顺序。1. 算法实现publicclassTopologicalSort{/** * param adj 邻接表 * return 拓扑序列如果图有环则返回 null */publicstaticint[]topologicalSort(ListInteger[]adj){intnadj.length;int[]inDegreenewint[n];// 1. 计算所有顶点的入度for(inti0;in;i){for(intv:adj[i]){inDegree[v];}}// 2. 将入度为 0 的顶点入队QueueIntegerqueuenewLinkedList();for(inti0;in;i){if(inDegree[i]0){queue.offer(i);}}// 3. 逐个出队更新入度int[]resultnewint[n];intidx0;while(!queue.isEmpty()){intuqueue.poll();result[idx]u;for(intv:adj[u]){inDegree[v]--;if(inDegree[v]0){queue.offer(v);}}}returnidxn?result:null;}}2. 应用场景课程安排先修课程 → 后修课程 编译依赖头文件依赖顺序 任务调度有依赖关系的任务执行顺序四、408 考研经典真题题1Dijkstra 执行过程图有 5 个顶点 0-4邻接矩阵如下 0 1 2 3 4 0 0 2 6 4 0 1 ∞ 0 3 ∞ 7 2 ∞ ∞ 0 ∞ 5 3 ∞ ∞ 1 0 8 4 ∞ ∞ ∞ ∞ 0 求从顶点 0 出发到各点的最短路径。 过程 初始dist [0, 2, 6, 4, ∞] 选 1dist [0, 2, 5, 4, 9] (6→235, ∞→279) 选 3dist [0, 2, 5, 4, 8] (9→4812不变, 取之前更小的8) ... 最终dist [0, 2, 5, 4, 8]题2最小生成树权值计算用 Prim 算法求以下图的最小生成树权值 边集{(1,2,4), (1,3,3), (1,4,2), (2,3,5), (2,5,6), (3,4,7)} 从1开始 选 (1,4,2) → 加入4 选 (1,3,3) → 加入3 选 (1,2,4) → 加入2 选 (2,5,6) → 加入5 最小总权值 2346 15题3拓扑排序判断以下哪种情况存在拓扑排序 A. 有向完全图 → ❌ 有环 B. 有向无环图(DAG) → ✅ C. 无向图 → ❌ 不能定义方向 D. 有向强连通图 → ❌ 每对顶点互通一定有环五、408 考点总结必考大题 手算 Dijkstra 每一步的 dist[] 变化 手算最小生成树的构造过程 拓扑排序序列的生成 常考选择题 Dijkstra 能否处理负权边 → 不能 Floyd 能否处理负权边 → 能但不能有负环 唯一最小生成树的条件 → 所有边权不同 拓扑排序不唯一的条件 → 有多个入度为 0 的顶点总结最短路径 → Dijkstra单源无负权/ Floyd多源无负环 最小生成树 → Prim稠密图/ Kruskal稀疏图 拓扑排序 → 入度法有环则无解 觉得有用的话点赞 关注【张老师技术栈】吧每周更新 Java/Python/爬虫 实战干货不让你白来。