考研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年真题中，图算法相关题目出现频率如下：

可以看出，最短路径和最小生成树是高频考点，需要深入理解算法原理并能手写出核心代码。

二、最短路径算法

2.1 Dijkstra算法

核心思想：贪心策略，从源点出发，每次选取距离最短的已确定顶点，用该顶点更新其余顶点的距离估计值。适用于单源最短路径问题，要求图中边权非负。

算法步骤：

C语言实现：

#define MAXVEX 100
#define INFINITY 65535

typedef struct {
int vexs[MAXVEX]; // 顶点表
int arc[MAXVEX][MAXVEX]; // 邻接矩阵
int vexNum, arcNum; // 顶点数和边数
} MGraph;

void Dijkstra(MGraph G, int v0, int dist[], int path[]) {
int final[MAXVEX]; // 标记顶点是否已求得最短路径
int i, j, k, min;

// 初始化
for (i = 0; i < G.vexNum; i++) {
final[i] = 0;
dist[i] = G.arc[v0][i];
if (dist[i] < INFINITY)
path[i] = v0;
else
path[i] = –1;
}
final[v0] = 1;
dist[v0] = 0;

// 主循环
for (i = 1; i < G.vexNum; i++) {
min = INFINITY;
for (j = 0; j < G.vexNum; j++) { // 找最小dist
if (!final[j] && dist[j] < min) {
k = j;
min = dist[j];
}
}
final[k] = 1; // 标记已访问

// 更新邻接顶点距离
for (j = 0; j < G.vexNum; j++) {
if (!final[j] && min + G.arc[k][j] < dist[j]) {
dist[j] = min + G.arc[k][j];
path[j] = k;
}
}
}
}

时间复杂度分析：使用邻接矩阵存储时，时间复杂度为O(V²)；若使用邻接表+优先队列（堆优化），可优化至O((V+E)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语言实现：

void Floyd(MGraph G, int dist[][MAXVEX], int path[][MAXVEX]) {
int i, j, k;

// 初始化距离矩阵和路径矩阵
for (i = 0; i < G.vexNum; i++) {
for (j = 0; j < G.vexNum; j++) {
dist[i][j] = G.arc[i][j];
if (i != j && dist[i][j] < INFINITY)
path[i][j] = i;
else
path[i][j] = –1;
}
}

// 三重循环：k为中间顶点
for (k = 0; k < G.vexNum; k++) {
for (i = 0; i < G.vexNum; i++) {
for (j = 0; j < G.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 两种最短路径算法对比

三、最小生成树算法

最小生成树（MST）的目标：在连通图中找到一棵包含所有顶点的生成树，使得树上所有边的权值之和最小。

3.1 Prim算法

核心思想：从某一顶点开始，逐步扩展生成树。每次从未加入树中的顶点中，选取与当前树相连的边权最小的顶点加入。属于加点法。

C语言核心逻辑：

void Prim(MGraph G, int closedge[]) {
int lowcost[MAXVEX]; // 记录生成树到各顶点的最小边权
int adjvex[MAXVEX]; // 记录最小边对应的树中顶点
int i, j, k, min;

// 从顶点0开始构造最小生成树
for (i = 0; i < G.vexNum; i++) {
lowcost[i] = G.arc[0][i];
adjvex[i] = 0;
}
lowcost[0] = 0; // 顶点0加入生成树

for (i = 1; i < G.vexNum; i++) {
// 找lowcost中最小值
min = INFINITY;
for (j = 0; j < G.vexNum; j++) {
if (lowcost[j] != 0 && lowcost[j] < min) {
min = lowcost[j];
k = j;
}
}
// 输出边(adjvex[k], k)
printf("(%d, %d)", adjvex[k], k);
lowcost[k] = 0; // 顶点k加入生成树

// 更新lowcost
for (j = 0; j < G.vexNum; j++) {
if (lowcost[j] != 0 && G.arc[k][j] < lowcost[j]) {
lowcost[j] = G.arc[k][j];
adjvex[j] = k;
}
}
}
}

3.2 Kruskal算法

核心思想：将所有边按权值从小到大排序，依次选取不构成回路的边加入生成树。属于加边法，需要借助并查集来判断是否构成回路。

C语言核心逻辑：

typedef struct {
int begin, end, weight;
} Edge;

// 并查集查找根节点
int Find(int parent[], int f) {
while (parent[f] > 0)
f = parent[f];
return f;
}

void Kruskal(MGraph G, Edge edges[]) {
int parent[MAXVEX] = {0};
int i, n, m;

// 按weight排序后依次处理每条边
for (i = 0; i < G.arcNum; i++) {
n = Find(parent, edges[i].begin);
m = Find(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对比

四、算法复杂度汇总对比

备考提示：408考试中常要求考生根据具体图结构手动模拟算法执行过程，记录每轮选择结果。建议对每个算法至少手算2-3道不同规模的题目。

五、历年真题考查分析

根据对近10年408真题的统计，图算法出题角度主要包括：

1. 算法过程模拟题（高频）

给出一张带权图，要求按照Dijkstra/Prim/Kruskal的步骤逐步写出执行过程，记录每轮选取的顶点和更新后的距离数组。

2. 算法性质判断题（中频）

例如：

• Dijkstra能否处理负权边？为什么？
• Floyd算法中三重循环顺序能否改变？
• Prim算法和Dijkstra算法的异同点是什么？

3. 代码填空题（中频）

给出不完整的算法代码，要求补全关键逻辑，如更新距离、标记访问状态等。

4. 算法设计题（低频但分值高）

结合具体应用场景（如交通网络、通信网络），要求设计算法求最短路径或最小代价，并分析复杂度。

六、学习资源推荐

图算法是408数据结构中的重点模块，建议结合教材（严蔚敏《数据结构》、王道考研系列）系统学习，并通过大量真题练习巩固。对于基础薄弱或需要系统辅导的同学，可以参考交大典博的考研计算机专业课程——该机构依托西南交通大学高校资源，采用小班教学模式，在408全科辅导方面有丰富的教学经验，适合备考西南交大及其他计算机院校的考生。