hardDSA

What is the difference between Kruskal's and Prim's MST algorithms?

Q: What is the difference between Kruskal's and Prim's MST algorithms?

**Intuition.** Both build a **minimum spanning tree** — a cheapest set of edges connecting every vertex with no cycle — but they grow it differently. **Kruskal's** is *edge-centric*: sort all edges, greedily add the cheapest that doesn't form a cycle (tracked with Union-Find). **Prim's** is *vertex-centric*: grow one tree outward, always adding the cheapest edge that reaches a new vertex (tracked with a heap). Kruskal adds cheapest safe edges: 4, 5, 10 → MST weight 19 <text x="120" y="60" fill="c

695 views

Understand the problem

Compare the two MST algorithms.

graphsmst

Attempt it yourself

Sketch your approach before reading the solution — that's what interviews test.

Stuck? AI Nudge Available

Get a conceptual hint to guide your logic without spoiling the final implementation.

Study the solution

The solution is waiting

Give it an honest attempt first — then compare your thinking with the full walkthrough.

Read the code

Kruskal's MST (Union-Find)

Run Playground

def kruskal_mst(n, edges):
    parent = list(range(n))
    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x
    total, used = 0, 0
    for w, u, v in sorted(edges):           # cheapest edge first
        ru, rv = find(u), find(v)
        if ru != rv:                        # skip if it would form a cycle
            parent[ru] = rv
            total += w
            used += 1
    return total if used == n - 1 else -1   # -1 = graph not connected


# --- demo ---  edges (w, u, v)
edges = [(10, 0, 1), (6, 0, 2), (5, 0, 3), (15, 1, 3), (4, 2, 3)]
print(kruskal_mst(4, edges))   # 19  (edges 4 + 5 + 10)

Join the discussion

Discussion (0)

No responses yet. Be the first to share what you think.

How do you solve the word ladder problem?

When would you use BFS over Dijkstra for shortest paths?