Prim’s Algorithm

 avatar
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);
}