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

class DisjointSet:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, node):
        if self.parent[node] != node:
            self.parent[node] = self.find(self.parent[node])  # Path compression
        return self.parent[node]

    def union(self, u, v):
        root_u = self.find(u)
        root_v = self.find(v)

        if root_u != root_v:
            if self.rank[root_u] > self.rank[root_v]:
                self.parent[root_v] = root_u
            elif self.rank[root_u] < self.rank[root_v]:
                self.parent[root_u] = root_v
            else:
                self.parent[root_v] = root_u
                self.rank[root_u] += 1

def kruskal(n, edges):
    """
    :param n: Number of nodes in the graph
    :param edges: List of edges (u, v, weight)
    :return: Minimum spanning tree and its cost
    """
    edges.sort(key=lambda x: x[2])  # Sort edges by weight
    ds = DisjointSet(n)
    mst = []
    total_weight = 0

    for u, v, weight in edges:
        if ds.find(u) != ds.find(v):  # If adding this edge doesn't form a cycle
            ds.union(u, v)
            mst.append((u, v, weight))
            total_weight += weight

    return mst, total_weight

# Example Graph (Undirected Weighted Graph)
edges = [
    (0, 1, 10), (0, 2, 6), (0, 3, 5),
    (1, 3, 15), (2, 3, 4)
]
num_nodes = 4

# Compute Minimum Spanning Tree
mst, total_weight = kruskal(num_nodes, edges)

# Output
print("Minimum Spanning Tree:", mst)
print("Total Weight of MST:", total_weight)