Kruskal vs Prim Algorithm: Key Differences and When to Use Each

The Kruskal algorithm builds a minimum spanning tree by sorting edges and adding the smallest edges without cycles, while the Prim algorithm grows the tree by adding the nearest vertex to the existing tree. Kruskal works well with sparse graphs, and Prim is efficient for dense graphs.

Quick Comparison

Here is a quick side-by-side comparison of Kruskal and Prim algorithms based on key factors.

Factor	Kruskal Algorithm	Prim Algorithm
Approach	Edge-based, sorts all edges	Vertex-based, grows tree from a start vertex
Data Structure Used	Disjoint Set (Union-Find)	Priority Queue (Min-Heap)
Graph Type Efficiency	Better for sparse graphs	Better for dense graphs
Cycle Detection	Explicitly checks using Union-Find	Implicit, by only adding adjacent vertices
Starting Point	No fixed start vertex needed	Requires a start vertex
Algorithm Type	Greedy, global edge sorting	Greedy, local vertex expansion

Key Differences

Kruskal algorithm sorts all edges by weight and adds them one by one to the growing forest, ensuring no cycles form by using a disjoint set data structure. It treats the graph as a collection of edges and connects components gradually.

In contrast, Prim algorithm starts from a chosen vertex and grows the minimum spanning tree by repeatedly adding the closest vertex not yet in the tree. It uses a priority queue to pick the next minimum edge connected to the tree.

Kruskal is often simpler to implement when edges are already sorted or easy to sort, and it works well on graphs with fewer edges. Prim is more efficient on dense graphs because it avoids sorting all edges upfront and focuses on vertices connected to the current tree.

Code Comparison

Here is a Python implementation of the Kruskal algorithm to find a minimum spanning tree.

python

class DisjointSet:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * 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:
            return False
        if self.rank[root_u] < self.rank[root_v]:
            self.parent[root_u] = root_v
        elif self.rank[root_u] > self.rank[root_v]:
            self.parent[root_v] = root_u
        else:
            self.parent[root_v] = root_u
            self.rank[root_u] += 1
        return True

def kruskal(n, edges):
    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

# Example graph with 4 vertices and weighted edges
edges = [
    (0, 1, 10),
    (0, 2, 6),
    (0, 3, 5),
    (1, 3, 15),
    (2, 3, 4)
]

mst, weight = kruskal(4, edges)
print("Edges in MST:", mst)
print("Total weight:", weight)

Output

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

Prim Equivalent

Here is a Python implementation of the Prim algorithm for the same graph.

python

import heapq

def prim(n, graph):
    visited = [False] * n
    min_heap = [(0, 0)]  # (weight, vertex)
    total_weight = 0
    mst = []
    prev = [None] * n

    while min_heap:
        w, u = heapq.heappop(min_heap)
        if visited[u]:
            continue
        visited[u] = True
        total_weight += w
        if w != 0:
            mst.append((prev[u], u, w))
        for v, weight in graph[u]:
            if not visited[v]:
                heapq.heappush(min_heap, (weight, v))
                prev[v] = u

    return mst, total_weight

# Graph as adjacency list: vertex -> list of (neighbor, weight)
graph = {
    0: [(1, 10), (2, 6), (3, 5)],
    1: [(0, 10), (3, 15)],
    2: [(0, 6), (3, 4)],
    3: [(0, 5), (1, 15), (2, 4)]
}

mst, weight = prim(4, graph)
print("Edges in MST:", mst)
print("Total weight:", weight)

Output

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

When to Use Which

Choose Kruskal algorithm when your graph is sparse, meaning it has relatively few edges compared to vertices, or when edges are already sorted or easy to sort. It is also preferred if you want a simple implementation that works well with disconnected graphs.

Choose Prim algorithm when your graph is dense, with many edges, because it avoids sorting all edges upfront and efficiently grows the tree from a starting vertex. Prim is also better when you have an adjacency list or matrix representation and want to start from a specific node.

Key Takeaways

Kruskal sorts edges and uses union-find to avoid cycles, ideal for sparse graphs.

Prim grows the tree vertex by vertex using a priority queue, efficient for dense graphs.

Kruskal does not require a start vertex; Prim needs one.

Use Kruskal for disconnected graphs or when edges are pre-sorted.

Use Prim when working with adjacency structures and dense graphs.