Scribd
Upload
7 views2 pages

Kruskal's Algorithm for MST in C

This C program implements Kruskal's algorithm to find the Minimum Spanning Tree (MST) of a graph. It prompts the user for the number of vertices and edges, then collects edge data, sorts the edges by weight, and uses a union-find structure to avoid cycles while constructing the MST. Finally, it outputs the edges included in the MST and the total cost.

Uploaded by

Dhwani agarwal
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as TXT, PDF, TXT or read online on Scribd
7 views2 pages

Kruskal's Algorithm for MST in C

This C program implements Kruskal's algorithm to find the Minimum Spanning Tree (MST) of a graph. It prompts the user for the number of vertices and edges, then collects edge data, sorts the edges by weight, and uses a union-find structure to avoid cycles while constructing the MST. Finally, it outputs the edges included in the MST and the total cost.

Uploaded by

Dhwani agarwal
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as TXT, PDF, TXT or read online on Scribd

#include <stdio.

h>

int main() {
int n, e;
printf("Enter number of vertices: ");
scanf("%d", &n);

printf("Enter number of edges: ");


scanf("%d", &e);

int u[e], v[e], w[e];


int i, j;

printf("\nEnter edges (u v w):\n");


for (i = 0; i < e; i++) {
scanf("%d %d %d", &u[i], &v[i], &w[i]);
}

/* Step 1: Sort edges based on weight (Bubble Sort) */


for (i = 0; i < e - 1; i++) {
for (j = 0; j < e - i - 1; j++) {
if (w[j] > w[j + 1]) {
int temp = w[j];
w[j] = w[j + 1];
w[j + 1] = temp;

temp = u[j];
u[j] = u[j + 1];
u[j + 1] = temp;

temp = v[j];
v[j] = v[j + 1];
v[j + 1] = temp;
}
}
}

/* Step 2: Kruskal – Used parent[] for cycle checking */


int parent[n];
for (i = 0; i < n; i++)
parent[i] = i;

int find, x, y;
int mst_cost = 0;

printf("\nEdges in MST:\n");

for (i = 0; i < e; i++) {


/* Find parent of u[i] */
x = u[i];
while (parent[x] != x)
x = parent[x];

/* Find parent of v[i] */


y = v[i];
while (parent[y] != y)
y = parent[y];

if (x != y) { // no cycle
printf("%d -- %d (weight %d)\n", u[i], v[i], w[i]);
mst_cost += w[i];
parent[y] = x; // union
}
}

printf("\nTotal cost of MST = %d\n", mst_cost);

return 0;
}

You might also like