题库 – 王码在线编程

图统计

在一个无向带权图中，若使用 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;

}

A graph[u][v] && !inMST[v] && graph[u][v] < minEdge[v]

B !inMST[v] && graph[u][v] < minEdge[v]

C graph[u][v] > 0 && !inMST[v]

D graph[u][v] > 0 && !inMST[v]

意见反馈

意见反馈