在一个无向带权图中，若使用 Prim 算法从顶点 0 开始构造最小生成树（边权均为正整数，且 graph[u][v] == 0 表示无边），下列代码中横线处应填入（ ）。 int prim(vector>& graph, int n) { vector inMST(n, false); vector 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;
A：graph[u][v] && !inMST[v] && graph[u][v] 0 && !inMST[v]
D：!inMST[v] && minEdge[v] > 0
正确答案：A
答案解析
Prim算法从顶点0开始，维护一个集合inMST表示已在生成树中的顶点，minEdge数组记录各顶点到生成树的最小边权。每轮选择未加入生成树且minEdge值最小的顶点u，将其加入生成树，并更新所有与其邻接且未加入生成树的顶点v：若边(u,v)存在且其权值小于当前minEdge[v]，则用该权值更新minEdge[v]。图中graph[u][v]为0表示无边，因此需判断graph[u][v] > 0。更新条件需确保v不在生成树中且新边权有效且更小。
试卷来源：202603 CCF-GESP编程能力等级认证C++八级真题