#include <stdio.h>
int findParent(int parent[], int i) {
if (parent[i] == i){
return i;
}
return findParent(parent, parent[i]);
}
int main() {
int e,v,i, j, tempCost,tempDs,tempSrc,weight = 0;
printf("how many vertices are there:");
scanf("%d", &v);
printf("how many edges are there:");
scanf("%d", &e);
int cost[10], src[10], ds[10],mst_src[10], mst_ds[10],mst_cost[10],parent[10];
for (i = 1; i <= v; i++) {
parent[i] = i;
}
for (i = 0; i < e; i++) {
printf("enter source, destination, Weight for edge %d:", i + 1);
scanf("%d %d %d", &src[i], &ds[i], &cost[i]);
}
for (i = 1; i < e; i++) {
for (j = 0; j < i; j++) {
if (cost[j] > cost[i]) {
tempCost = cost[i];
cost[i] = cost[j];
cost[j] = tempCost;
tempSrc = src[i];
src[i] = src[j];
src[j] = tempSrc;
tempDs = ds[i];
ds[i] = ds[j];
ds[j] = tempDs;
}
}
}
j = 0;
for (i = 0; i < e; i++) {
if (findParent(parent, src[i]) != findParent(parent, ds[i])) {
weight += cost[i];
mst_src[j] = src[i];
mst_ds[j] = ds[i];
mst_cost[j] = cost[i];
parent[findParent(parent,src[i])] = ds[i];
j++;
}
}
printf("\nTHE MINIMUM SPANNING TREE:\n");
for (i = 0; i < j; i++) {
printf("%d -----> %d cost = %d\n", mst_src[i], mst_ds[i], mst_cost[i]);
}
printf("\nTotal weight = %d", weight);
return 0;
}
