单选题

下面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;

}

A

graph[u][v] >= 0 && key[v] > graph[u][v]

B

graph[u][v] <= 0 && key[v] > graph[u][v]

C

graph[u][v] == 0 && key[v] > graph[u][v]

D

graph[u][v] != 0 && key[v] > graph[u][v]

赣ICP备20007335号-2