【研路导航】从容应对保研机试：最小生成树算法实践与解析

轻保研推出了VIP全流程辅导班，专注为大三的同学走好“保研最后一步”，同时为大一大二的同学提供了先人一步的机会，关注轻保研，回复【VIP圆梦班】了解VIP圆梦班的详细概况～

欢迎来到【研路导航】 栏目！在这里，我们汇集了各种实用的保研干货，包括面试技巧、时间规划、备考方法等。这里不仅有详细的策略分享，还有经验丰富的专家和学长学姐们为你解读和分析每个关键步骤。无论你是刚刚起步还是即将面临保研挑战， '研路导航' 将成为你的贴心顾问和可靠指南，助你在保研之路上游刃有余。

轻保研

研路导航

保研机试技巧

写在前面

在保研过程中，机试是一项重要的考核内容，特别是对于计算机相关专业的学生而言，机试成绩往往能起到决定性的作用。因此，掌握一些高效的算法和编程技巧对于在机试中取得好成绩至关重要。今天，我将与大家分享一些关于最小生成树（MST）相关的算法和机试技巧，希望能够帮助大家在备战保研机试时更加从容应对。

01

Prim算法

01

代码展示

/* * Prim求MST * 耗费矩阵cost[][]，初始化为INF，标号从0开始，0 ~ n－1 * 返回最小生成树的权值，返回-1表示原图不连通 */constint INF = 0x3f3f3f3f;constint MAXN = 110;bool vis[MAXN];int lowc[MAXN];int cost[MAXN][MAXN];
// 修正cost（添加边）voidupdata(int x, int y, int v){    cost[x - 1][y - 1] = v;    cost[y - 1][x - 1] = v;return;}
intPrim(int cost[][MAXN], int n){int ans = 0;memset(vis, false, sizeof(vis));    vis[0] = true;for (int i = 1; i < n; i++) {        lowc[i] = cost[0][i];    }for (int i = 1; i < n; i++) {int minc = INF;int p = -1;for (int j = 0; j < n; j++) {if (!vis[j] && minc > lowc[j]) {                minc = lowc[j];                p = j;            }        }if (minc == INF) {return-1; // 原图不连通        }        ans += minc;        vis[p] = true;for (int j = 0; j < n; j++) {if (!vis[j] && lowc[j] > cost[p][j]) {                lowc[j] = cost[p][j];            }        }    }return ans;}

02

代码解析

初始化常量与变量

constint INF = 0x3f3f3f3f;constint MAXN = 110;bool vis[MAXN];int lowc[MAXN];int cost[MAXN][MAXN];

这段代码首先定义了常量INF和MAXN，分别表示无穷大和最大节点数。接着，定义了三个数组vis、lowc和cost，分别表示节点是否被访问、最小边权值和图的邻接矩阵。

修正边权值函数

voidupdata(int x, int y, int v){    cost[x - 1][y - 1] = v;    cost[y - 1][x - 1] = v;return;}

updata函数用于修正边权值，将节点x和节点y之间的边权值设为v，注意节点编号从1开始，因此在访问数组时减1。

Prim算法核心部分

intPrim(int cost[][MAXN], int n){int ans = 0;memset(vis, false, sizeof(vis));    vis[0] = true;for (int i = 1; i < n; i++) {        lowc[i] = cost[0][i];    }for (int i = 1; i < n; i++) {int minc = INF;int p = -1;for (int j = 0; j < n; j++) {if (!vis[j] && minc > lowc[j]) {                minc = lowc[j];                p = j;            }        }if (minc == INF) {return-1; // 原图不连通        }        ans += minc;        vis[p] = true;for (int j = 0; j < n; j++) {if (!vis[j] && lowc[j] > cost[p][j]) {                lowc[j] = cost[p][j];            }        }    }return ans;}

算法首先初始化访问数组vis和lowc数组。然后，从节点0开始，逐步将未访问的节点加入到生成树中。每次选取未访问节点中与生成树相连的最小边，并更新相应的边权值，直至所有节点都被访问。

03

机试技巧

1、掌握基础算法：熟练掌握基础算法如Prim和Kruskal，并能根据题目要求灵活应用。

2、代码模板准备：准备好常用算法的代码模板，在机试中可以节省大量时间。

3、注重细节：注意节点编号、初始化以及边界条件等细节，避免不必要的错误。

4、多练习：通过刷题平台进行多次练习，积累经验，提高编程速度和准确性。

02

Kruskal算法

01

代码展示

/* * Kruskal算法求MST * 对边操作，并排序 * 切记：初始化赋值问题（tol） */constint MAXN = 110; // 最大点数constint MAXM = 10000; // 最大边数int F[MAXN]; // 并查集使用structEdge {int u; // 起点int v; // 终点int w; // 权值} edge[MAXM]; // 存储边的信息int tol; // 边数，加边前赋值为0
voidaddEdge(int u, int v, int w){    edge[tol].u = u;    edge[tol].v = v;    edge[tol++].w = w;}
boolcmp(Edge a, Edge b){// 排序函数，将边按照权值从小到大排序return a.w < b.w;}
intfind(int x){if (F[x] == x) {return x;    } else {return F[x] = find(F[x]);    }}
intKruskal(int n){for (int i = 0; i <= n; i++) {        F[i] = i;    }    sort(edge, edge + tol, cmp);int cnt = 0; // 计算加入的边数int ans = 0;for (int i = 0; i < tol; i++) {int u = edge[i].u;int v = edge[i].v;int w = edge[i].w;int tOne = find(u);int tTwo = find(v);if (tOne != tTwo) {            ans += w;            F[tOne] = tTwo;            cnt++;        }if (cnt == n - 1) {break;        }    }if (cnt < n - 1) {return-1; // 不连通    } else {return ans;    }}

02

代码解析

初始化常量与变量

constint MAXN = 110; // 最大点数constint MAXM = 10000; // 最大边数int F[MAXN]; // 并查集使用structEdge {int u; // 起点int v; // 终点int w; // 权值} edge[MAXM]; // 存储边的信息int tol; // 边数，加边前赋值为0

定义了常量MAXN和MAXM，分别表示最大节点数和最大边数。并查集数组F和边数组edge用于存储边的信息。

添加边与排序函数

voidaddEdge(int u, int v, int w){    edge[tol].u = u;    edge[tol].v = v;    edge[tol++].w = w;}
boolcmp(Edge a, Edge b){// 排序函数，将边按照权值从小到大排序return a.w < b.w;}

addEdge函数用于添加边的信息，而cmp函数用于对边进行权值从小到大的排序。

并查集查找与Kruskal算法核心部分

intfind(int x){if (F[x] == x) {return x;    } else {return F[x] = find(F[x]);    }}
intKruskal(int n){for (int i = 0; i <= n; i++) {        F[i] = i;    }    sort(edge, edge + tol, cmp);int cnt = 0; // 计算加入的边数int ans = 0;for (int i = 0; i < tol; i++) {int u = edge[i].u;int v = edge[i].v;int w = edge[i].w;int tOne = find(u);int tTwo = find(v);if (tOne != tTwo) {            ans += w;            F[tOne] = tTwo;            cnt++;        }if (cnt == n - 1) {break;        }    }if (cnt < n - 1) {return-1; // 不连通    } else {return ans;    }}

并查集的find函数用于查找节点的根节点，并进行路径压缩。Kruskal算法通过对边进行排序，然后逐步将最小权值的边加入到生成树中，确保不形成环，直到生成树包含n-1条边。

03

机试技巧

1、熟悉并查集：并查集是Kruskal算法的核心，熟练掌握路径压缩和合并操作是关键。

2、善用排序函数：在处理边的权值时，合理使用排序函数可以大大简化代码复杂度。

3、边界条件处理：注意初始化和边界条件的处理，确保算法的正确性和完整性。

4、多加练习：通过多次练习，熟悉并查集和Kruskal算法的实现过程，提高编程速度和准确性。

写在最后

机试题目往往需要我们在短时间内完成高效的代码编写和优化。通过掌握和练习经典算法，如Prim和Kruskal算法，我们可以在保研机试中占据优势。在此过程中，注重代码的规范性和细节处理，才能确保在关键时刻发挥出最佳水平。希望今天的分享对大家有所帮助，祝大家在保研路上顺利！

以上就是保研机试的技巧分享，想要获取更多保研干货，可以看看我们新推出的《轻保研·一步到位资料包》！

7 大核心资料包，全方位助力保研成功！

全面覆盖：

1、保研理念指南：从基础到高阶，全面解析保研流程和时间节点。

2、一站式备考宝典：专业课复习资料、常见面试题库，备考无忧。

3、英语口语大师手册：口语技巧、实战策略与题库示例，轻松应对英语面试。

4、前辈经验秘籍：100+位学长学姐的亲身经验和成功心得，一手掌握。

5、保研面试共题攻略：院校专业问题详解，实战计划与答题技巧，面试无惧。

6、文书模板框架：个人陈述、简历和文书模板，完美呈现自我。

7、机试知识模板：ACM模板、机械技巧和算法经典，让你脱颖而出。

突破备考难关，拿下保研offer！

在公众号后台回复【一步到位资料包】或者扫码上方二维码领取《轻保研·一步到位资料包》，一研为定！