数据结构：kruskal算法

分手后的思念是犯贱 2022-05-30 05:54 158阅读 0赞

#include <stdio.h>
    #include <stdlib.h>
    #include <algorithm>
    using namespace std;
    
    typedef struct {
        int begin;
        int end;
        int weight;
    } Edge;
    int father[1005];
    
    void init() {
        for (int i=0; i<1005; i++) {
            father[i] = i;
        }
    }
    
    int find(int x) {
        return father[x] == x ? x : father[x] = find(father[x]);
    }
    
    void join (int x, int y) {
        int p1 = find(x);
        int p2 = find(y);
    
        if (p1 == p2) {
            return ;
        }
        father[p1] = p2;
    }
    
    void kruskal (Edge edges[], int n, int m) {
        int sum_weight = 0;
        int num = 0;
        init();
        for (int i=0; i<m; i++) {
            if (find(edges[i].begin) != find(edges[i].end)) {
                printf("%d %d %d\n", edges[i].begin, edges[i].end, edges[i].weight);
                sum_weight += edges[i].weight;
                num++;
                join(edges[i].begin, edges[i].end);
            }
            if (num >= n-1) { break; }
        }
        printf("weight of MST is %d\n", sum_weight);
    
    }
    
    bool cmp (Edge a, Edge b) {
        return a.weight < b.weight;
    }
    
    int main (int argc, char **argv) {
        int n, m;//顶点、边
        Edge edges[20];
        scanf("%d %d", &n, &m);
        for (int i=0; i<m; i++) {
            scanf("%d %d %d", &edges[i].begin, &edges[i].end, &edges[i].weight);
        }
        sort(edges, edges+m, cmp);
        printf("kruskal:\n");
        kruskal(edges, n,  m);
        return 0;
    }
    /*
    9 15
    4 7 7
    2 8 8
    0 1 10
    0 5 11
    1 8 12
    3 7 16
    1 6 16
    5 6 17
    1 2 18
    6 7 19
    3 4 20
    3 8 21
    2 3 22
    3 6 24
    4 5 26
    */
    /*
    99
    */