Prim’s Algorithm

user_3763047219
c_cpp
2 years ago
1.8 kB
3
Indexable
Never
```#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);
}
```