Kruskal Algorithm: What It Is and How It Works

The Kruskal algorithm is a method to find the minimum spanning tree of a graph by selecting edges in order of increasing weight without forming cycles. It helps connect all points with the least total cost by adding the smallest edges one by one.

How It Works

Imagine you want to connect several cities with roads so that every city is reachable from any other, but you want to spend the least money possible. The Kruskal algorithm helps by looking at all possible roads (edges) and picking the cheapest ones first.

It starts by sorting all roads by their cost. Then, it adds the cheapest road to the network if it doesn't create a loop. This process repeats until all cities are connected. This way, you get a network that connects everything with the minimum total cost.

Example

This example shows how Kruskal algorithm finds the minimum spanning tree for a graph with weighted edges.

python

class DisjointSet:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

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

    def union(self, x, y):
        rootX = self.find(x)
        rootY = self.find(y)
        if rootX == rootY:
            return False
        if self.rank[rootX] < self.rank[rootY]:
            self.parent[rootX] = rootY
        elif self.rank[rootX] > self.rank[rootY]:
            self.parent[rootY] = rootX
        else:
            self.parent[rootY] = rootX
            self.rank[rootX] += 1
        return True

def kruskal(edges, n):
    edges.sort(key=lambda x: x[2])  # Sort by weight
    ds = DisjointSet(n)
    mst = []
    total_weight = 0
    for u, v, w in edges:
        if ds.union(u, v):
            mst.append((u, v, w))
            total_weight += w
    return mst, total_weight

# Graph edges: (node1, node2, weight)
graph_edges = [
    (0, 1, 4),
    (0, 2, 3),
    (1, 2, 1),
    (1, 3, 2),
    (2, 3, 4),
    (3, 4, 2),
    (4, 5, 6)
]

mst, weight = kruskal(graph_edges, 6)
print("Edges in MST:", mst)
print("Total weight:", weight)

Output

Edges in MST: [(1, 2, 1), (1, 3, 2), (3, 4, 2), (0, 2, 3), (4, 5, 6)]
Total weight: 14

When to Use

Use Kruskal algorithm when you need to connect all points in a network with the smallest total connection cost, such as designing road systems, computer networks, or electrical grids. It works best when the graph edges are already sorted or can be sorted efficiently.

It is especially useful when the graph is sparse (has fewer edges) because it processes edges one by one. If you want to find the cheapest way to link all locations without any loops, Kruskal is a great choice.

Key Points

• Kruskal algorithm finds a minimum spanning tree by adding edges in increasing order of weight.
• It avoids cycles by using a disjoint set (union-find) data structure.
• It works well for sparse graphs and when edges can be sorted easily.
• The result is a tree connecting all nodes with minimum total edge weight.

Key Takeaways

Kruskal algorithm builds a minimum spanning tree by adding the smallest edges without creating cycles.

It uses a union-find structure to efficiently check and avoid loops.

Best suited for sparse graphs or when edges can be sorted quickly.

It ensures all nodes are connected with the least total edge cost.