Prim’s Algorithm
user_3763047219
c_cpp
2 years ago
1.8 kB
6
Indexable
#include <iostream> int main() { int n = 0, m = 0, s = 0; scanf("%d %d", &n, &m); int weight[201][3] = {}; int key[201] = {}; for (int i = 1; i <= m; i++) { scanf("%d %d %d", &weight[i][0], &weight[i][1], &weight[i][2]); } for (int i = 1; i <= n; i++) { key[i] = 10001; } scanf("%d", &s); key[s] = 0; int count = 1; int v[201] = { 0 }; int parent[201] = { 0 }; v[s] = 1; while (count <= n) { int eachkey = 10001; for (int i = 1; i <= m; i++) { if (weight[i][0] == s|| weight[i][1] == s) { if (weight[i][0] == s) { if (v[weight[i][1]] == 0) { if (key[weight[i][1]] > weight[i][2]) { key[weight[i][1]] = weight[i][2]; parent[weight[i][1]] = s; } } } else if (weight[i][1] == s) { if (v[weight[i][0]] == 0) { if (key[weight[i][0]] > weight[i][2]) { key[weight[i][0]] = weight[i][2]; parent[weight[i][0]] = s; } } } } } for (int i = 1; i <= n; i++) { if (v[i] == 0) { if (eachkey > key[i]) { eachkey = key[i]; s = i; } } } v[s] = 1; count = count + 1; } for (int i = 1; i < n; i++) { printf("%d ", parent[i]); } printf("%d\n", parent[n]); int sum = 0; for (int i = 1; i <= n; i++) { sum = sum + key[i]; } printf("%d", sum); }
Editor is loading...