Find minimum spanning tree using kruskal algorith in c Language
#include <stdio.h>
int find(int i, int parent[]) {
while (parent[i] != i)
i = parent[i];
return i;
}
void union_set(int i, int j, int parent[]) {
int a = find(i, parent);
int b = find(j, parent);
parent[b] = a;
}
void kruskal(int n, int edges[20][3], int e) {
int parent[20];
int i, j, u, v, cost = 0, count = 0;
// Step 1: MakeSet(v) → initialize parent[i] = i
for (i = 1; i <= n; i++)
parent[i] = i;
// Step 2: Sort edges in ascending order of weight
for (i = 0; i < e - 1; i++) {
for (j = i + 1; j < e; j++) {
if (edges[i][2] > edges[j][2]) {
int temp0 = edges[i][0];
int temp1 = edges[i][1];
int temp2 = edges[i][2];
edges[i][0] = edges[j][0];
edges[i][1] = edges[j][1];
edges[i][2] = edges[j][2];
edges[j][0] = temp0;
edges[j][1] = temp1;
edges[j][2] = temp2;
}
}
}
printf("\nEdges in the Minimum Spanning Tree:\n");
// Step 3: For each edge (u,v) in ascending order
for (i = 0; i < e; i++) {
u = edges[i][0];
v = edges[i][1];
// Step 4: If Find(u) ≠ Find(v)
if (find(u, parent) != find(v, parent)) {
printf("(%d, %d) cost = %d\n", u, v, edges[i][2]);
cost += edges[i][2];
count++;
union_set(u, v, parent);
}
if (count == n - 1)
break;
}
printf("\nTotal cost of Minimum Spanning Tree = %d\n", cost);
}
int main() {
int n, e, i;
int edges[20][3];
printf("Enter number of vertices: ");
scanf("%d", &n);
printf("Enter number of edges: ");
scanf("%d", &e);
printf("Enter edges (u v w):\n");
for (i = 0; i < e; i++) {
scanf("%d%d%d", &edges[i][0], &edges[i][1], &edges[i][2]);
}
kruskal(n, edges, e);
return 0;
}
Comments
Post a Comment