class Graph:

    def __init__(self, size):

        self.size = size

        self.edges = []  # For storing edges as (u, v, weight)

        self.vertex_data = [''] * size  # Store vertex names

​

    def add_edge(self, u, v, weight):

        if 0 <= u < self.size and 0 <= v < self.size:

            self.edges.append((u, v, weight))  # Add edge with weight

    def add_vertex_data(self, vertex, data):

        if 0 <= vertex < self.size:

            self.vertex_data[vertex] = data

​

    def find(self, parent, i):

        if parent[i] == i:

            return i

        return self.find(parent, parent[i])

​

    def union(self, parent, rank, x, y):

        xroot = self.find(parent, x)

        yroot = self.find(parent, y)

        if rank[xroot] < rank[yroot]:

            parent[xroot] = yroot

        elif rank[xroot] > rank[yroot]:

            parent[yroot] = xroot

        else:

            parent[yroot] = xroot

            rank[xroot] += 1

​

    def kruskals_algorithm(self):

        result = []  # MST

        i = 0  # edge counter

​

        self.edges = sorted(self.edges, key=lambda item: item[2])

​

        parent, rank = [], []

​

        for node in range(self.size):

            parent.append(node)

            rank.append(0)

​

        while i < len(self.edges):

            u, v, weight = self.edges[i]

            i += 1

            x = self.find(parent, u)

            y = self.find(parent, v)

            if x != y:

                result.append((u, v, weight))

                self.union(parent, rank, x, y)

​

#include <stdio.h>

#include <stdlib.h>

​

// Structure to represent an edge

typedef struct {

    int u, v, weight;

} Edge;

​

// Structure to represent a graph

typedef struct {

    int size;

    Edge* edges;

    char** vertex_data;

    int edgeCount;

} Graph;

​

// Function prototypes

void initGraph(Graph* g, int size);

void addEdge(Graph* g, int u, int v, int weight);

void addVertexData(Graph* g, int vertex, const char* data);

int find(int parent[], int i);

void unionSet(int parent[], int rank[], int x, int y);

void kruskalsAlgorithm(Graph* g);

int compareEdges(const void* a, const void* b);

​

void initGraph(Graph* g, int size) {

    g->size = size;

    g->edges = (Edge*)malloc(size * size * sizeof(Edge)); // Assuming maximum possible edges

    g->vertex_data = (char**)malloc(size * sizeof(char*));

    g->edgeCount = 0;

}

​

void addEdge(Graph* g, int u, int v, int weight) {

    g->edges[g->edgeCount].u = u;

    g->edges[g->edgeCount].v = v;

    g->edges[g->edgeCount].weight = weight;

    g->edgeCount++;

}

​

void addVertexData(Graph* g, int vertex, const char* data) {

    g->vertex_data[vertex] = (char*)malloc(2 * sizeof(char)); // Assuming single character names

    sprintf(g->vertex_data[vertex], "%s", data);

}

​

int find(int parent[], int i) {

    if (parent[i] == i)

        return i;

    return find(parent, parent[i]);

}

​

import java.util.ArrayList;

import java.util.Collections;

​

public class Main {

    static class Edge implements Comparable<Edge> {

        int src, dest, weight;

​

        public int compareTo(Edge compareEdge) {

            return this.weight - compareEdge.weight;

        }

    }

​

    static class Subset {

        int parent, rank;

    }

​

    static class Graph {

        int V; // Number of vertices

        ArrayList<Edge> edges; // Collection of all edges

        String[] vertexNames; // Store vertex names for printout

​

        Graph(int v) {

            V = v;

            edges = new ArrayList<>();

            vertexNames = new String[V];

        }

​

        void addEdge(int src, int dest, int weight) {

            Edge newEdge = new Edge();

            newEdge.src = src;

            newEdge.dest = dest;

            newEdge.weight = weight;

            edges.add(newEdge);

        }

​

        void addVertexName(int vertex, String name) {

            vertexNames[vertex] = name;

        }

​

        // Make find method similar to Python's, using path compression

        int find(Subset subsets[], int i) {

            if (subsets[i].parent != i)

                subsets[i].parent = find(subsets, subsets[i].parent);

            return subsets[i].parent;

        }

​

        // Simplify union method to match Python's logic more closely

        void union(Subset subsets[], int x, int y) {

            int xRoot = find(subsets, x);

            int yRoot = find(subsets, y);

​

            // Attach smaller rank tree under root of high rank tree