Sign in
Skip to solution
hardDSA

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

696 views
01

Understand the problem

Compare the two MST algorithms.

graphsmst
02

Attempt it yourself

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

Nudge consolestandby

Stuck? Beam a request up — the console returns a conceptual nudge that guides your logic without spoiling the implementation.

03

Study the solution

Both build a minimum spanning tree. Kruskal's sorts edges and adds the cheapest that doesn't form a cycle (using Union-Find) — great for sparse graphs, O(E log E). Prim's grows a tree from one node, always adding the cheapest boundary edge via a heap — O(E log V), better for dense graphs.

Solution ready — 2 min read

Classified // press E to declassify

04

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)
05

Join the discussion

Discussion (0)

Sign in to join the discussion.

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

Transmission complete // awaiting log

KEEP THE
STREAK ALIVE.

Dossier 114 of 127 decoded in the Data Structures & Algorithms track. One more won't hurt.

Back to track