GESP 八级 · GESP 202603 C++ 八级 第 13 题

在一个无向带权图中，若使用 Prim 算法从顶点 $0$ 开始构造最小生成树（边权均为正整数，且 graph[u][v] == 0 表示无边），下列代码中横线处应填入（ ）。

int prim(vector<vector<int>>& graph, int n) {
    vector<bool> inMST(n, false);
    vector<int> minEdge(n, INT_MAX);
    minEdge[0] = 0;
    int result = 0;
    for (int i = 0; i < n; i++) {
        int u = -1;
        for (int j = 0; j < n; j++)
            if (!inMST[j] && (u == -1 || minEdge[j] < minEdge[u]))
                u = j;
        inMST[u] = true;
        result += minEdge[u];
        for (int v = 0; v < n; v++)
            if (__________) // 在此处填入选项
                minEdge[v] = graph[u][v];
    }
    return result;
}

STL 容器：vector（动态数组）、set/map（红黑树，有序）、unordered_set/map（哈希表，无序）。注意迭代器失效问题。

填空时注意语法完整性：分号、括号匹配、函数参数类型和个数、返回值类型。

【考点】Prim算法｜最小生成树｜贪心策略

🎯 考纲定位

本题考查《GESP 考试大纲》八级图论模块中Prim算法的具体实现细节。命题人把这道题放在这里，专门卡住那些"背过算法思想但没写过代码"的考生——很多人知道Prim是贪心选最小边，却对邻接矩阵中"无边即0"的特殊约定毫无警惕。

🧠 解题思维

Prim算法的核心循环是：每轮选一个未入树的最小边顶点，然后用新顶点的所有邻边去松弛其他顶点。松弛的前提有三： 1. 边必须存在（邻接矩阵中 graph[u][v] > 0） 2. 目标顶点尚未入树（!inMST[v]） 3. 新边更优（graph[u][v] < minEdge[v]） 缺少任一条件都会破坏最小生成树的正确性。

🪤 陷阱拆解

• 选项B去掉了graph[u][v]，把无边当成权重0，导致minEdge[v]被错误更新为0，破坏后续选择。
• 选项C缺少与minEdge[v]的比较，松弛成了无条件赋值，贪心性质失效。
• 选项D直接忽略边权，只判断非树状态，minEdge永远停留在INT_MAX或旧值，算法彻底崩坏。

最阴险的细节是邻接矩阵约定0表示无边，而INT_MAX才是无穷大，两者绝对不能混用。

🔄 反命题思维

若把邻接矩阵换成邻接表，条件退化为graph[u][v] < minEdge[v]；若把题目改成"求最小生成树边数而非总权"，只需去掉result += minEdge[u]一行。这类题刷到先问自己：数据结构和边界约定是否已完全适配算法原始逻辑。