DSA Kruskal’s Algorithm

Welcome to TheCodingCollege.com! In this post, we will explore Kruskal’s Algorithm, an efficient way to find the Minimum Spanning Tree (MST) of a graph. Kruskal’s Algorithm is a foundational concept in Data Structures and Algorithms (DSA) and is widely used in optimization problems.

What is Kruskal’s Algorithm?

Kruskal’s Algorithm is a greedy algorithm that constructs the MST of a graph by sorting its edges by weight and adding them to the MST, provided they do not form a cycle. The algorithm works well for sparse graphs and is edge-focused.

Key Characteristics of Kruskal’s Algorithm

1. Edge-Based Approach: Works on edges instead of vertices.
2. Greedy Strategy: Always chooses the smallest available edge.
3. Cycle Prevention: Uses the Union-Find (Disjoint-Set) data structure to avoid cycles.

Steps of Kruskal’s Algorithm

1. Sort Edges: Arrange all edges in ascending order by weight.
2. Initialize: Start with an empty MST.
3. Add Edges: Iterate through the sorted edges and add them to the MST if they don’t form a cycle.
4. Cycle Detection: Use the Union-Find data structure to check for cycles.
5. Terminate: Repeat until the MST contains V−1V – 1 edges (where VV is the number of vertices).

Applications of Kruskal’s Algorithm

• Network Design: Optimizing communication or transportation networks.
• Clustering: Hierarchical clustering in machine learning.
• Resource Allocation: Efficiently connecting nodes in distributed systems.

Implementation of Kruskal’s Algorithm

Python Code Implementation

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

    def add_edge(self, u, v, weight):
        self.edges.append((weight, u, v))

    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 kruskal_mst(self):
        self.edges.sort()
        parent = []
        rank = []
        mst = []
        total_weight = 0

        for node in range(self.vertices):
            parent.append(node)
            rank.append(0)

        for weight, u, v in self.edges:
            x = self.find(parent, u)
            y = self.find(parent, v)

            if x != y:
                mst.append((u, v, weight))
                total_weight += weight
                self.union(parent, rank, x, y)

        return mst, total_weight

# 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, total_weight = g.kruskal_mst()
print("Edges in MST:", mst)
print("Total Weight of MST:", total_weight)

Dry Run Example

Graph Example

• Vertices: 0,1,2,3
• Edges:
  • (0,1,10)
  • (0,2,6)
  • (0,3,5)
  • (1,3,15)
  • (2,3,4)

Steps:

1. Sort edges by weight: (2,3,4),(0,3,5),(0,2,6),(0,1,10),(1,3,15)
2. Add (2,3,4)(2, 3, 4): MST = [(2,3)]
3. Add (0,3,5)(0, 3, 5): MST = [(2,3),(0,3)]
4. Add (0,1,10)(0, 1, 10): MST = [(2,3),(0,3),(0,1)]

Result: MST Edges = (2,3),(0,3),(0,1)(2, 3), (0, 3), (0, 1), Total Weight = 4+5+10=19.

Time Complexity

• Sorting Edges: O(Elog⁡E)O(E \log E), where EE is the number of edges.
• Union-Find Operations: O(Elog⁡V)O(E \log V), where VV is the number of vertices.

Comparison: Kruskal’s vs Prim’s Algorithm

Advantages of Kruskal’s Algorithm

1. Works well for sparse graphs.
2. Easier to implement for adjacency list representations.
3. Provides flexibility in starting with any edge.

Disadvantages of Kruskal’s Algorithm

1. Sorting edges can be computationally expensive for dense graphs.
2. Requires an additional data structure (Union-Find).

Real-World Applications

• Road and Communication Networks: Optimizing routes and reducing costs.
• Clustering Algorithms: Used in hierarchical clustering.
• Distributed Systems: Connecting nodes efficiently.

Conclusion

Kruskal’s Algorithm is an efficient and straightforward approach to finding the Minimum Spanning Tree of a graph. Its edge-based methodology makes it ideal for sparse graphs. Mastering Kruskal’s Algorithm is essential for solving complex optimization problems in graph theory.