Python - Kruskal's Algorithm for Minimum Spanning Trees

Kruskal's algorithm is a widely used technique for finding the Minimum Spanning Tree (MST) of a connected, undirected graph. MST is a subgraph that includes all vertices of the original graph with the minimum possible sum of edge weights. Kruskal's algorithm is efficient and works well for sparse graphs. Here's an example:

Example - Finding Minimum Spanning Tree with Kruskal's Algorithm in Python:

class Graph:
    def __init__(self, vertices):
        self.V = vertices
        self.graph = []

    def add_edge(self, u, v, w):
        self.graph.append([u, v, w])

    def kruskal_mst(self):
        def find(parent, i):
            if parent[i] == i:
                return i
            return find(parent, parent[i])

        def union(parent, rank, x, y):
            x_root = find(parent, x)
            y_root = find(parent, y)

            if rank[x_root] < rank[y_root]:
                parent[x_root] = y_root
            elif rank[x_root] > rank[y_root]:
                parent[y_root] = x_root
            else:
                parent[y_root] = x_root
                rank[x_root] += 1

        result = []
        i = 0
        e = 0

        self.graph = sorted(self.graph, key=lambda item: item[2])
        parent = [i for i in range(self.V)]
        rank = [0] * self.V

        while e < self.V - 1:
            u, v, w = self.graph[i]
            i += 1
            x = find(parent, u)
            y = find(parent, v)

            if x != y:
                e += 1
                result.append([u, v, w])
                union(parent, rank, x, y)

        return result

# Example usage:
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)

mst = g.kruskal_mst()
for u, v, weight in mst:
    print(f"Edge: {u} - {v}, Weight: {weight}")

In this example, we use Kruskal's algorithm to find the Minimum Spanning Tree of a graph represented by an adjacency list. The algorithm starts with an empty MST and iteratively adds the smallest available edges while ensuring that no cycles are formed.

Kruskal's algorithm is valuable for optimizing network design, cluster analysis, and various applications involving connected graphs. It provides an efficient way to find the minimum spanning tree in a graph.