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.
Top comments (0)