Minimum Spanning Tree (Kruskal's Algorithm)

Question 1

When is Kruskal preferred over Prim?

Accepted Answer

Sparse graphs — Kruskal is O(E log E), better for sparse graphs where E is small. Prim is O(E log V), better for dense graphs.

Question 2

A Minimum Spanning Tree (MST) of a connected weighted graph is…

Accepted Answer

Connects all vertices with minimum total edge weight, no cycles — An MST connects every vertex using exactly V−1 edges, forms no cycle (it's a tree), and minimizes the sum of edge weights.

Question 3

How many edges does an MST of a graph with V vertices have?

Accepted Answer

Exactly V minus 1 edges total — A spanning tree over V vertices always has exactly V−1 edges — enough to connect all vertices with no cycle.

Question 4

Kruskal's algorithm builds an MST by…

Accepted Answer

Sorting edges, adding the cheapest that avoids a cycle — Kruskal's greedily adds globally lightest edges, skipping those that would create a cycle (detected via Union-Find), until V−1 edges are chosen.

Question 5

Prim's algorithm builds an MST by…

Accepted Answer

Growing outward from a start vertex, cheapest edge each step — Prim's starts from a vertex and expands the tree by the minimum-weight edge connecting the tree to an outside vertex — a frontier-growth greedy.

Question 6

Kruskal's time complexity is dominated by…

Accepted Answer

Sorting the edges, roughly O(E log E) — Sorting the E edges costs O(E log E); the Union-Find operations add only a near-linear factor, so Kruskal's is O(E log E).

Question 7

Prim's with a binary heap runs in…

Accepted Answer

O(E log V) — Each edge can trigger a heap update (O(log V)) and each vertex is extracted once: O(E log V). With a Fibonacci heap it's O(E + V log V).

Question 8

The 'cut property' guarantees that…

Accepted Answer

The lightest edge crossing any cut belongs in some MST — For any partition of vertices, the lightest edge crossing the cut is safe to add — the theoretical justification for both Prim's and Kruskal's greedy choices.

Question 9

When all edge weights are DISTINCT, the MST is…

Accepted Answer

Unique — Distinct weights force a single optimal choice at each step (no ties), so the MST is unique.

Question 10

Is an MST the same as a shortest-path tree from a source?

Accepted Answer

No, they optimize genuinely different objectives — They optimize different things: MST minimizes the sum of chosen edges; a shortest-path tree minimizes each vertex's distance from the root. They can differ.

Kruskal’s algorithm

Test your knowledge

When is Kruskal preferred over Prim?

The short version

In more depth

Two Approaches

When to reach for this

Interview Questions

References & Further Reading

Related topics

Love this visualization?