Kruskal’s Algorithm

    #include <stdio.h>
    #include <conio.h>
    #include <stdlib.h>

    int i, j, k, a, b, u, v, n, ne = 1;
    int min, mincost = 0, cost[9][9], parent[9];
    int find(int);
    int uni(int, int);
    void main() {
      printf("\n\tImplementation of Kruskal's Algorithm\n");
      printf("\nEnter the no. of vertices:");
      scanf("%d", & n);
      printf("\nEnter the cost adjacency matrix:\n");
      for (i = 1; i <= n; i++) {
        for (j = 1; j <= n; j++) {
          scanf("%d", & cost[i][j]);
          if (cost[i][j] == 0)
            cost[i][j] = 999;
        }
      }
      printf("The edges of Minimum Cost Spanning Tree are\n");
      while (ne < n) {
        for (i = 1, min = 999; i <= n; i++) {
          for (j = 1; j <= n; j++) {
            if (cost[i][j] < min) {
              min = cost[i][j];
              a = u = i;
              b = v = j;
            }
          }
        }
        u = find(u);
        v = find(v);
        if (uni(u, v)) {
          printf("%d edge (%d,%d) =%d\n", ne++, a, b, min);
          mincost += min;
        }
        cost[a][b] = cost[b][a] = 999;
      }
      printf("\n\tMinimum cost = %d\n", mincost);
      getch();
    }
    int find(int i) {
      while (parent[i])
        i = parent[i];
      return i;
    }
    int uni(int i, int j) {
      if (i != j) {
        parent[j] = i;
        return 1;
      }
      return 0;
    }

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// Define a structure to represent an edge
struct Edge {
    int src, dest, weight;
};

// Define a structure to represent a graph
class Graph {
public:
    int V, E; // Number of vertices and edges
    vector<Edge> edges; // Collection of all edges

    Graph(int V, int E);
    void addEdge(int src, int dest, int weight);
};

// Constructor
Graph::Graph(int V, int E) {
    this->V = V;
    this->E = E;
}

// Function to add an edge to the graph
void Graph::addEdge(int src, int dest, int weight) {
    edges.push_back({src, dest, weight});
}

// Find set of an element i (uses path compression technique)
int find(vector<int>& parent, int i) {
    if (parent[i] != i)
        parent[i] = find(parent, parent[i]);
    return parent[i];
}

// Do union of two sets (uses union by rank)
void Union(vector<int>& parent, vector<int>& rank, int x, int y) {
    int rootX = find(parent, x);
    int rootY = find(parent, y);

    if (rootX != rootY) {
        if (rank[rootX] > rank[rootY])
            parent[rootY] = rootX;
        else if (rank[rootX] < rank[rootY])
            parent[rootX] = rootY;
        else {
            parent[rootY] = rootX;
            rank[rootX]++;
        }
    }
}

// Compare two edges according to their weights
bool compare(Edge a, Edge b) {
    return a.weight < b.weight;
}

// Function to perform Kruskal's algorithm
void KruskalMST(Graph& graph) {
    int V = graph.V;
    vector<Edge> result; // Store the resultant MST
    int e = 0; // An index variable for result[]

    // Step 1: Sort all the edges in non-decreasing order of their weight
    sort(graph.edges.begin(), graph.edges.end(), compare);

    // Allocate memory for creating V subsets
    vector<int> parent(V);
    vector<int> rank(V, 0);

    // Create V single-item sets
    for (int v = 0; v < V; ++v)
        parent[v] = v;

    // Number of edges to be taken is equal to V-1
    for (auto edge : graph.edges) {
        if (e >= V - 1)
            break;

        int u = find(parent, edge.src);
        int v = find(parent, edge.dest);

        // If including this edge does not cause cycle, include it in result
        if (u != v) {
            result.push_back(edge);
            Union(parent, rank, u, v);
            e++;
        }
    }

    // Print the contents of result[] to display the built MST
    cout << "Following are the edges in the constructed MST:\n";
    for (auto edge : result)
        cout << edge.src << " -- " << edge.dest << " == " << edge.weight << endl;
}

int main() {
    int V = 7; // Number of vertices
    int E = 11; // Number of edges
    Graph graph(V, E);

    // Add edges to the graph
    graph.addEdge(0, 1, 7);
    graph.addEdge(0, 3, 5);
    graph.addEdge(1, 2, 8);
    graph.addEdge(1, 3, 9);
    graph.addEdge(1, 4, 7);
    graph.addEdge(2, 4, 5);
    graph.addEdge(3, 4, 15);
    graph.addEdge(3, 5, 6);
    graph.addEdge(4, 5, 8);
    graph.addEdge(4, 6, 9);
    graph.addEdge(5, 6, 11);

    // Perform Kruskal's algorithm
    KruskalMST(graph);

    return 0;
}