Kruskal_MST_Algorithm

pwnmelife

#include <stdio.h>
#include <stdlib.h>

#define MaxVertexNum 100
#define Infiniate 65535
typedef bool VertexType;
typedef int EdgeType;


typedef struct {
        int start;
        int end;
        int weight;
}EdgeArray;


EdgeArray* InitKruskal(int Edgenumber);
void MSTKruskal(EdgeArray *D, int Edgenumber, int VertexNumber);
int Find(int *parent, int vertex);

int main()
{

        EdgeArray* D;
        int Edgenumber;
        int VertexNumber;
        printf("Please input the Edgenumber and VertexNumber\n");
        scanf("%d%d", &Edgenumber, &VertexNumber);
        D = InitKruskal(Edgenumber);
        printf("The Kruskal result:\n");
        MSTKruskal(D, Edgenumber, VertexNumber);
}


EdgeArray* InitKruskal(int Edgenumber) {
        printf("Please input a edgedarray, according to from small to large\n");
        printf("for example: start end weight\n");
        int start, end, weight;
        EdgeArray *D = (EdgeArray *)malloc(sizeof(EdgeArray) * Edgenumber);
        for (int i = 0; i < Edgenumber; i++) {
                scanf("%d%d%d", &start, &end, &weight);
                (D + i)->start = start;
                (D + i)->end = end;
                (D + i)->weight = weight;
        }
        return D;
}
void MSTKruskal(EdgeArray *D, int Edgenumber, int VertexNumber) {
        int n, m;
        int parent[MaxVertexNum];
        for (int i = 0; i < VertexNumber; i++) {
                *(parent + i) = 0;
        }
        for (int j = 0; j < Edgenumber; j++) {
                n = Find(parent, (D + j)->start);
                m = Find(parent, (D + j)->end);
                if (n != m) {
                        parent[n] = m;
                        printf("%d %d %d\n", (D + j)->start, (D + j)->end, (D + j)->weight);
                }
        }
}
//Find函数最为神奇
int Find(int *parent, int f) {
        while (*(parent + f) > 0) {
                f = *(parent + f);
        }
        return f;
}
/*
 输入: 10 6
0 2 1
3 5 2
1 4 3
2 5 4
2 3 5
1 2 5
0 3 5
0 1 6
2 4 6
4 5 6
输出:
0 2 1
3 5 2
1 4 3
2 5 4
1 2 5
 */