Kruskal_MST_Algorithm

#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);
        }
    }
}
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
 */