//Program of krushkal algorithm
#include <stdio.h>
#include <stdlib.h>
#define V 5 // Number of vertices
#define E 6 // Number of edges
// Structure to represent a graph edge
typedef struct Edge {
int u, v, weight;
} Edge;
// Structure to represent a disjoint set
typedef struct DisjointSet {
int parent[V];
} DisjointSet;
// Function to create a disjoint set
DisjointSet* createDisjointSet() {
DisjointSet* ds = (DisjointSet*) malloc(sizeof(DisjointSet));
for (int i = 0; i < V; i++) {
ds->parent[i] = i;
}
return ds;
}
// Function to find the parent of a vertex
int find(DisjointSet* ds, int i) {
if (ds->parent[i] == i) return i;
return find(ds, ds->parent[i]);
}
// Function to merge two sets
void union1(DisjointSet* ds, int x, int y) {
int xroot = find(ds, x);
int yroot = find(ds, y);
ds->parent[xroot] = yroot;
}
// Function to implement Kruskal's algorithm
void kruskal(Edge* edges, int numEdges) {
DisjointSet* ds = createDisjointSet();
Edge* result = (Edge*) malloc(sizeof(Edge) * (V-1));
int i, j;
for (i = 0; i < V-1; i++) {
int min = -1;
for (j = 0; j < numEdges; j++) {
if (find(ds, edges[j].u) != find(ds, edges[j].v)) {
if (min == -1 || edges[j].weight < edges[min].weight) {
min = j;
}
}
}
result[i] = edges[min];
union1(ds, edges[min].u, edges[min].v);
}
printf("Minimum Spanning Tree:\n");
for (i = 0; i < V-1; i++) {
printf("%d - %d = %d\n", result[i].u, result[i].v, result[i].weight);
}
}
int main() {
Edge edges[] = {
{0, 1, 2},
{0, 2, 4},
{1, 2, 1},
{1, 3, 3},
{2, 3, 5},
{3, 4, 2}
};
int numEdges = sizeof(edges) / sizeof(edges[0]);
kruskal(edges, numEdges);
return 0;
}
