GESP 八级 · GESP 202509 C++ 八级 第 14 题

下面 Prim 算法程序中，横线处应该填入的是（ ）。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int prim(vector<vector<int>> & graph, int n) {
    vector<int> key(n, INT_MAX);
    vector<int> parent(n, -1);
    key[0] = 0;
    for (int i = 0; i < n; i++) {
        int u = min_element(key.begin(), key.end()) - key.begin();
        if (key[u] == INT_MAX)
            break;
        for (int v = 0; v < n; v++) {
            if (__________) { // 在此处填入选项
                key[v] = graph[u][v];
                parent[v] = u;
            }
        }
    }
    int sum = 0;
    for (int i = 0; i < n; i++) {
        if (parent[i] != -1) {
            cout << "Edge: " << parent[i] << " - " << i << " Weight: " << key[i] << endl;
            sum += key[i];
        }
    }
    return sum;
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> graph(n, vector<int>(n, 0));
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        graph[u][v] = w;
        graph[v][u] = w;
    }
    int result = prim(graph, n);
    cout << "Total weight of the minimum spanning tree: " << result << endl;
    return 0;
}

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

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

【考点】Prim算法｜最小生成树｜邻接矩阵语义

GESP 八级图论模块核心题型，命题人刻意用邻接矩阵替代优先队列，考察学生在无显式数据结构时能否通过矩阵非零元素判断连通性。

Prim 算法本质是"每次选最小权边连接树与非树节点"。key[v] 记录当前 v 到树的最小边权，更新条件必须包含两层约束：1) v 尚未入树（通过 graph[u][v] != 0 判断，因为输入矩阵中 0 代表无边）；2) 新边更优（key[v] > graph[u][v]）。注意外层循环已确保 u 是当前树中节点，内层只需检查 u 与 v 是否连通。

逐个排查选项：A 项 >=0 恒成立（权值非负），导致对已入树节点也更新，破坏 MST 构造；B、C 项 <0 或 ==0 仅检查无边情况，完全反向；D 项 !=0 精准命中"存在边"这一连通性条件，配合贪心更新，构成标准 Prim 逻辑。

若将图改为邻接表存储，横线处应改为 graph[u].count(v) && key[v] > graph[u][v]；若矩阵初始化非 0 而是 -1，则需改为 graph[u][v] >= 0。刷到此类题，先问自己"矩阵里什么值代表连通"。