Krushkal algorithm

 //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;

}