Kruskal’s Algorithm#

Welcome to Day 45 of our 60 Days of Coding Algorithm Challenge! Today, we’ll explore Kruskal’s Algorithm, another greedy algorithm used for finding the Minimum Spanning Tree (MST) of a weighted undirected graph.

What is Kruskal’s Algorithm?#

Kruskal’s Algorithm is a minimum-spanning-tree algorithm which finds an edge of the least possible weight that connects any two trees in the forest. It is a greedy algorithm in graph theory as it finds a minimum spanning tree for a connected weighted graph adding increasing cost arcs at each step.

How Kruskal’s Algorithm Works#

1. Sort all the edges from low weight to high.
2. Take the edge with the lowest weight and add it to the spanning tree. If adding the edge created a cycle, then reject this edge.
3. Keep adding edges until we reach all vertices.

Implementation#

Let’s implement Kruskal’s Algorithm in Python:

 1class DisjointSet:
 2    def __init__(self, vertices):
 3        self.parent = {v: v for v in vertices}
 4        self.rank = {v: 0 for v in vertices}
 5
 6    def find(self, item):
 7        if self.parent[item] != item:
 8            self.parent[item] = self.find(self.parent[item])
 9        return self.parent[item]
10
11    def union(self, x, y):
12        xroot = self.find(x)
13        yroot = self.find(y)
14
15        if self.rank[xroot] < self.rank[yroot]:
16            self.parent[xroot] = yroot
17        elif self.rank[xroot] > self.rank[yroot]:
18            self.parent[yroot] = xroot
19        else:
20            self.parent[yroot] = xroot
21            self.rank[xroot] += 1
22
23def kruskal(graph):
24    edges = [(cost, u, v) for u in graph for v, cost in graph[u].items()]
25    edges.sort()
26    vertices = list(graph.keys())
27    
28    ds = DisjointSet(vertices)
29    mst = []
30
31    for cost, u, v in edges:
32        if ds.find(u) != ds.find(v):
33            ds.union(u, v)
34            mst.append((u, v, cost))
35
36    return mst
37
38# Example usage
39graph = {
40    'A': {'B': 2, 'C': 3},
41    'B': {'A': 2, 'C': 1, 'D': 1, 'E': 4},
42    'C': {'A': 3, 'B': 1, 'F': 5},
43    'D': {'B': 1, 'E': 1},
44    'E': {'B': 4, 'D': 1, 'F': 1},
45    'F': {'C': 5, 'E': 1}
46}
47
48minimum_spanning_tree = kruskal(graph)
49print("Edges in the Minimum Spanning Tree:")
50for u, v, cost in minimum_spanning_tree:
51    print(f"{u} -- {v}: {cost}")

Time Complexity#

The time complexity of Kruskal’s algorithm is O(E log E) or O(E log V), where E is the number of edges and V is the number of vertices. This is because:

• Sorting the edges takes O(E log E) time.
• The disjoint-set operations (find and union) take O(log V) time per operation.

Space Complexity#

O(V), where V is the number of vertices in the graph, for the disjoint-set data structure.

Advantages of Kruskal’s Algorithm#

1. Efficient for sparse graphs
2. Easy to implement
3. Can be used to find Maximum Spanning Trees by negating edge weights

Comparison with Prim’s Algorithm#

• Kruskal’s algorithm is generally faster for sparse graphs.
• Prim’s algorithm is generally faster for dense graphs.
• Kruskal’s builds the MST by adding edges, while Prim’s builds it by adding vertices.

Applications#

1. Network design (e.g., designing a least-cost network)
2. Clustering algorithms
3. Approximation algorithms for NP-hard problems (e.g., traveling salesman problem)
4. Image segmentation in computer vision

Exercise#

1. Implement Kruskal’s algorithm using an edge list representation instead of an adjacency list.
2. Modify the algorithm to find the Maximum Spanning Tree instead of the Minimum Spanning Tree.
3. Implement a function that compares the MSTs generated by Prim’s and Kruskal’s algorithms for the same graph.

Summary#

Today, we explored Kruskal’s Algorithm, another fundamental graph algorithm for finding Minimum Spanning Trees. We implemented the algorithm, discussed its time and space complexity, and looked at its advantages and applications.

Understanding Kruskal’s Algorithm, along with Prim’s Algorithm from yesterday, provides a comprehensive toolkit for solving problems related to Minimum Spanning Trees and network optimization.

Tomorrow, we’ll dive into another important graph algorithm: the Floyd-Warshall Algorithm. Stay tuned!

Solution#

 1class DisjointSet:
 2    def __init__(self, vertices):
 3        self.parent = {v: v for v in vertices}
 4        self.rank = {v: 0 for v in vertices}
 5
 6    def find(self, item):
 7        if self.parent[item] != item:
 8            self.parent[item] = self.find(self.parent[item])  # path compression
 9        return self.parent[item]
10
11    def union(self, x, y):
12        xr, yr = self.find(x), self.find(y)
13        if xr == yr:
14            return False  # already connected, would form a cycle
15        if self.rank[xr] < self.rank[yr]:
16            xr, yr = yr, xr
17        self.parent[yr] = xr
18        if self.rank[xr] == self.rank[yr]:
19            self.rank[xr] += 1
20        return True
21
22def kruskal_edge_list(vertices, edges):
23    # edges is a list of (u, v, cost) tuples
24    ds = DisjointSet(vertices)
25    mst = []
26    for u, v, cost in sorted(edges, key=lambda e: e[2]):
27        if ds.union(u, v):          # union returns False if it would form a cycle
28            mst.append((u, v, cost))
29    return mst
30
31# Example usage
32vertices = ['A', 'B', 'C', 'D', 'E', 'F']
33edges = [
34    ('A', 'B', 2), ('A', 'C', 3), ('B', 'C', 1), ('B', 'D', 1),
35    ('B', 'E', 4), ('C', 'F', 5), ('D', 'E', 1), ('E', 'F', 1)
36]
37for u, v, cost in kruskal_edge_list(vertices, edges):
38    print(f"{u} -- {v}: {cost}")