### Kruskal Algorithm Implementation in Python To implement the Kruskal algorithm for finding Minimum Spanning Tree (MST) in Python, one can use an edge list representation of graphs. An edge list consists of tuples representing edges which contain the source node, destination node, and edge weight[^2]. Here is how this might be implemented: ```python class Graph: def __init__(self, vertices): self.V = vertices # Number of vertices self.graph = [] # List to store graph's edges # Function to add an edge into the graph def add_edge(self, u, v, w): self.graph.append([u, v, w]) # A utility function to find set of an element i # (uses path compression technique) def find(self, parent, i): if parent[i] == i: return i return self.find(parent, parent[i]) # A function that does union of two sets of x and y # (uses union by rank) def union(self, parent, rank, x, y): root_x = self.find(parent, x) root_y = self.find(parent, y) if rank[root_x] < rank[root_y]: parent[root_x] = root_y elif rank[root_x] > rank[root_y]: parent[root_y] = root_x else: parent[root_y] = root_x rank[root_x] += 1 # The main function to construct MST using Kruskal's algorithm def kruskal_mst(self): result = [] # This will store the resultant MST # An index variable, used for sorted edges i = 0 # An index variable, used for result[] e = 0 # Step 1: Sort all the edges based on their weights. self.graph = sorted(self.graph, key=lambda item: item[2]) parent = [] rank = [] # Create V subsets with single elements for node in range(self.V): parent.append(node) rank.append(0) # Number of edges to be taken is equal to V-1 while e < self.V - 1: # Step 2: Pick the smallest edge and increment # the index for next iteration u, v, w = self.graph[i] i = i + 1 x = self.find(parent, u) y = self.find(parent, v) # If including this edge doesn't cause cycle, # include it in result and increment the index # of result for next edge if x != y: e = e + 1 result.append([u, v, w]) self.union(parent, rank, x, y) # Else discard the edge minimumCost = 0 print("Edges in the constructed MST") for u, v, weight in result: minimumCost += weight print("%d -- %d == %d" % (u, v, weight)) print("Minimum Cost Spanning Tree", minimumCost) # Driver code g = Graph(4) g.add_edge(0, 1, 10) g.add_edge(0, 2, 6) g.add_edge(0, 3, 5) g.add_edge(1, 3, 15) g.add_edge(2, 3, 4) g.kruskal_mst() ``` This program defines a `Graph` class containing methods necessary for implementing Kruskal’s algorithm. It initializes the graph object with a specified number of vertices and allows adding weighted edges between these nodes through its method `add_edge`. After setting up the graph structure, calling `kruskal_mst()` computes the MST according to Kruskal’s approach.