下面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;
}
graph[u][v] >= 0 && key[v] > graph[u][v]
graph[u][v] <= 0 && key[v] > graph[u][v]
graph[u][v] == 0 && key[v] > graph[u][v]
graph[u][v] != 0 && key[v] > graph[u][v]