Kruskal’s Algorithm

Kruskal’s Algorithm is a greedy algorithm used to find a Minimum Spanning Tree (MST) for a weighted, connected, and undirected graph. It works by sorting all edges by weight and adding them one by one while ensuring no cycles are formed.

Concept

Kruskal’s Algorithm follows these principles:

1. Sort all edges in non-decreasing order of weight.
2. Select the smallest edge that does not form a cycle.
3. Repeat until the MST contains exactly (N - 1) edges, where N is the number of vertices.

The algorithm uses the Union-Find data structure to efficiently check and merge connected components.

Algorithm Steps

1. Initialize an empty set for the MST.
2. Sort all edges by weight.
3. Iterate through edges:
   • If the edge connects two different components, add it to the MST.
   • Merge the components using the Union-Find data structure.
4. Repeat until the MST contains (N - 1) edges.

Example

Consider the following weighted graph:

Vertex Pair	Edge Weight
A - B	4
A - C	3
B - C	1
B - D	2
C - D	5

Applying Kruskal’s Algorithm:

1. Sort edges by weight: B - C (1), B - D (2), A - C (3), A - B (4), C - D (5).
2. Add B - C (1) (smallest edge).
3. Add B - D (2) (next smallest).
4. Add A - C (3) (next smallest, does not form a cycle).
5. The MST is complete with edges B - C, B - D, A - C.

Total MST weight: 1 + 2 + 3 = 6

Implementation

A simple implementation of Kruskal’s Algorithm in Python:

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))

    def find(self, u):
        if self.parent[u] != u:
            self.parent[u] = self.find(self.parent[u])
        return self.parent[u]

    def union(self, u, v):
        root_u = self.find(u)
        root_v = self.find(v)
        if root_u != root_v:
            self.parent[root_u] = root_v

def kruskal_mst(edges, n):
    edges.sort(key=lambda x: x[2])
    uf = UnionFind(n)
    mst = []
    
    for u, v, weight in edges:
        if uf.find(u) != uf.find(v):
            uf.union(u, v)
            mst.append((u, v, weight))
        if len(mst) == n - 1:
            break

    return mst

edges = [(0, 1, 4), (0, 2, 3), (1, 2, 1), (1, 3, 2), (2, 3, 5)]
mst = kruskal_mst(edges, 4)
print("Minimum Spanning Tree:", mst)

Properties

• Greedy Algorithm
  • Always selects the smallest available edge at each step.
• Cycle Prevention
  • Uses Union-Find to prevent cycles in the MST.
• Efficiency
  • Runs in O(E log E) time complexity due to sorting.

Applications

• Network Design
  • Used to design cost-efficient communication and transportation networks.
• Cluster Analysis
  • Forms the basis of some hierarchical clustering techniques.
• Approximation Algorithms
  • Helps solve NP-hard problems like the Traveling Salesman Problem.

See Also

• Minimum Spanning Tree
• Prim’s Algorithm
• Borůvka’s Algorithm
• Greedy Algorithm
• Graph Theory