Scribd
Upload
5 views2 pages

Kruskal's Algorithm for Minimal Spanning Tree

The document provides a C program implementing Kruskal's algorithm to find the minimal spanning tree of a graph. It includes functions for finding the root of a vertex and performing union operations, as well as input handling for vertices and edges. The program outputs the edges of the minimum spanning tree and the total cost of the tree.

Uploaded by

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

Kruskal's Algorithm for Minimal Spanning Tree

The document provides a C program implementing Kruskal's algorithm to find the minimal spanning tree of a graph. It includes functions for finding the root of a vertex and performing union operations, as well as input handling for vertices and edges. The program outputs the edges of the minimum spanning tree and the total cost of the tree.

Uploaded by

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

ASSIGNMENT-15

Q. Find the minimal spanning tree by implementing Kruskal's


algorithm.

#include <stdio.h>
#define MAX 30
typedef struct {
int u, v, w;
} Edge;
int parent[MAX];
int find(int x) {
while (parent[x] != x)
x = parent[x];
return x;
}
void unionSet(int a, int b) {
int rootA = find(a);
int rootB = find(b);
parent[rootB] = rootA;
}
int main() {
int n, e;
Edge edges[MAX], mst[MAX];
printf("Enter number of vertices: ");
scanf("%d", &n);
printf("Enter number of edges: ");
scanf("%d", &e);
printf("Enter edges (u v weight):\n");
for (int i = 0; i < e; i++) {
scanf("%d %d %d", &edges[i].u, &edges[i].v, &edges[i].w);
}
for (int i = 0; i < n; i++)
parent[i] = i;
for (int i = 0; i < e - 1; i++) {
for (int j = 0; j < e - i - 1; j++) {
if (edges[j].w > edges[j + 1].w) {
Edge temp = edges[j];
edges[j] = edges[j + 1];
edges[j + 1] = temp;
}
}
}
int count = 0, totalCost = 0;
for (int i = 0; i < e; i++) {
int u = edges[i].u;
int v = edges[i].v;
if (find(u) != find(v)) {
mst[count++] = edges[i];
totalCost += edges[i].w;
unionSet(u, v);
}
}
printf("\nMinimum Spanning Tree (Kruskal's Algorithm):\n");
for (int i = 0; i < count; i++) {
printf("%d -- %d (weight = %d)\n", mst[i].u, mst[i].v, mst[i].w);
}
printf("\nTotal Minimum Cost = %d\n", totalCost);
return 0;
}

OUTPUT :

You might also like