#include <stdio.h>
int findParent(int parent[], int i) {
if (parent[i] == i) {
return i;
}
return findParent(parent, parent[i]);
}
int nearby(int src, int ds, int mst_src[], int mst_ds[], int j) {
for (int i = 0; i <= j; i++) {
if (src == mst_src[i] || src == mst_ds[i] || ds == mst_src[i] ||
ds == mst_ds[i] || j == 0) {
return 1;
}
}
return 0;
}
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;
while (j < v - 1) {
for (i = 0; i < e; i++) {
if (findParent(parent, src[i]) != findParent(parent, ds[i]) &&
nearby(src[i], ds[i], mst_src, mst_ds, j)) {
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++;
break;
}
}
}
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;
}
