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;
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 = 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
*/
页:
[1]