Kruskal's Algorithm and MST Explained: A Step-by-Step Worked Example

Learn what an MST is, how DSU makes Kruskal's cycle decisions, and how a seven-vertex graph reaches six selected edges with total weight 14.

KnowledgeGate Team

Exam prep & CS education

Updated 19 Nov 20265 min read
Kruskal's Algorithm and MST Explained: A Step-by-Step Worked Example

An MST is not merely a low-weight collection of edges. Kruskal's algorithm is also not simply "keep taking the smallest edge", because every choice must preserve acyclicity. The seven-vertex graph reaches an MST of weight 14 through sorted edges and cycle checks, illustrating selection-order, total-weight, and trap-based exam questions.

Minimum spanning trees: the object Kruskal is trying to build

A weighted, undirected graph uses two-way edges with weights. A spanning subgraph includes every vertex; connected means a path exists between each pair. A tree is connected and acyclic, while a cycle is a closed path. Total edge weight is the edge-weight sum.

For a connected graph with V vertices, every spanning tree has exactly V - 1 edges. A minimum spanning tree, or MST, has the smallest total weight. More than one tree may share that minimum.

For {P,Q,R} with PQ=2, QR=3, and PR=8, {PQ,QR} weighs 2+3=5. The alternatives weigh 2+8=10 and 3+8=11. An MST minimises the sum, not the largest edge alone.

The standard MST problem assumes a connected, undirected weighted graph. Review the graph traversal and shortest-path foundations, but distinguish the goals: an MST minimises total tree weight; a shortest-path tree preserves routes from one source.

Kruskal's algorithm: sorted edges plus disjoint sets

Kruskal grows a forest and has no starting vertex:

  1. Make one component per vertex.

  2. Sort edges by non-decreasing weight.

  3. Scan them in order.

  4. Accept only between different components, then merge them.

  5. Stop at V - 1 accepted edges.

A disjoint-set union structure, or DSU, makes the test efficient. find(x) identifies x's component representative. If find(u) == find(v), (u,v) would close a cycle; otherwise, union(u,v) merges the components. Union by rank or size and path compression are optimisations, not different greedy decisions.

The cut idea says the lightest available edge joining two current components is safe. This is the relevant greedy choice and exchange reasoning. "Smallest edges are always safe" is incomplete without the different-component condition.

Worked example: compute the MST edge by edge

Use vertices {A,B,C,D,E,F,G} and edges AB=4, AC=3, BC=1, BD=2, CD=4, CE=2, DE=3, DF=6, EF=5, EG=4, FG=2. Since V=7, the target is six accepted edges. One deterministic sorted order is:

BC(1), BD(2), CE(2), FG(2), AC(3), DE(3), AB(4), CD(4), EG(4), EF(5), DF(6)

Equal-weight edges may use another legal order. This order gives:

Edge

Weight

Find endpoints same?

Decision

Components after decision

Running MST weight

BC

1

No

Accept

{BC}, {A}, {D}, {E}, {F}, {G}

1

BD

2

No

Accept

{BCD}, {A}, {E}, {F}, {G}

3

CE

2

No

Accept

{BCDE}, {A}, {F}, {G}

5

FG

2

No

Accept

{BCDE}, {FG}, {A}

7

AC

3

No

Accept

{ABCDE}, {FG}

10

DE

3

Yes

Reject, cycle

{ABCDE}, {FG}

10

AB

4

Yes

Reject, cycle

{ABCDE}, {FG}

10

CD

4

Yes

Reject, cycle

{ABCDE}, {FG}

10

EG

4

No

Accept and stop

{ABCDEFG}

14

The edge set is {BC,BD,CE,FG,AC,EG}, with weight 1+2+2+2+3+4=14. After six acceptances, EF(5) and DF(6) remain unused.

Weighted graph with MST edges AC=3, BC=1, BD=2, CE=2, EG=4, and FG=2 highlighted green, totalling 14.
Kruskal/DSU timeline shows edges accepted in order, cycle rejections for DE(3), AB(4), and CD(4), and final connectivity of all seven vertices at total 14.

Why the result is correct, not just plausible

Before EG(4), the components are {A,B,C,D,E} and {F,G}. Their crossing edges are EG=4, EF=5, and DF=6, so EG is safe. Earlier acceptances pass the same component-crossing test.

Once {A,B,C,D,E} is connected, DE=3, AB=4, and CD=4 each closes a cycle. Rejection depends on current components, not apparent expense. At completion, all seven vertices share one component and 7-1=6 edges are accepted. These checks do not replace the algorithm on arbitrary input.

Ties, uniqueness, disconnected graphs, and Kruskal versus Prim

Equal weights are valid. Here BD, CE, and FG weigh 2, while AB, CD, and EG weigh 4. A written solution benefits from a fixed tie rule, but equal weights do not automatically mean multiple MSTs.

For example, in cycle P-Q-R-S-P, let PQ=QR=RS=SP=1 and PR=QS=2. Any three perimeter edges form an MST of weight 3, giving four MSTs. Distinct edge weights, however, guarantee a unique MST.

For a disconnected example, vertices {A,B,C,D,E} with AB=1, BC=2, AC=4, and DE=3 produce the minimum spanning forest {AB,BC,DE} of weight 1+2+3=6. No single spanning tree exists. Kruskal is edge-centric: it sorts all edges and joins DSU components. Prim's Algorithm and Minimum Spanning Tree owns the complementary frontier trace: it grows from one chosen vertex and updates the cheapest crossing edge. The minimum weight agrees, but the state you track is different.

Complexity and implementation checklist

Code
for each v in vertices: makeSet(v)
sort(edges) by numeric weight
mstWeight = 0; selectedEdges = 0
for (u, v, w) in edges:
    if find(u) != find(v):
        union(u, v)
        mstWeight += w; selectedEdges += 1
        if selectedEdges == V - 1: break
if selectedEdges != V - 1: report minimum spanning forest
else: report MST and mstWeight

Sorting costs O(E log E). Path compression plus union by rank or size makes DSU operations O(E alpha(V)) amortised. The usual total is O(E log E), with O(V) auxiliary DSU space apart from edges and result.

Traps include sorting weights as strings, applying Kruskal to a directed graph, forgetting isolated vertices, adding before checking representatives, unioning labels instead of roots, and reporting an MST with fewer than V - 1 accepted edges.

How exams test Kruskal and where marks are lost

Four checks follow from the graph. Through DE(3), five edges are accepted, one is rejected, weight is 10, and two components remain. AB(4) and CD(4) are then rejected. EG(4) completes six edges at weight 14.

Recurring past-paper-style forms, not a guaranteed paper pattern, ask for edge order, cost, components after k scans, first rejection, DSU state, uniqueness, or a changed weight. The traps have short fixes:

  • "Take the first V - 1 sorted edges": check components before every acceptance.

  • "Kruskal starts from the lightest vertex": it has no start vertex.

  • "Only a triangle can be a cycle": DSU detects cycles of any length.

  • "Negative edges break MST": they are valid and appear early in sorted order.

  • "Same weight means the same tree": a tie order can change the tree while preserving minimum weight.

Use the GATE CS courses and practice routes to place MST inside the wider syllabus, then use timed mock and subject-wise test practice to check whether the process still holds under time pressure.

Kruskal checkpoint: rebuild the trace after one weight changes

A reliable Kruskal trace has three checkpoints: the edge order is non-decreasing, every accepted edge joins different DSU representatives, and a connected graph stops after V - 1 acceptances. The accepted weights must sum to the reported total.

The result is {BC,BD,CE,FG,AC,EG}, total 14. Redraw the graph, hide the decisions, and rebuild the sorted list and DSU table. Then change EG from 4 to 7. After the same first five acceptances, EF=5 is the cheapest connection between {ABCDE} and {FG}. The new MST is {BC,BD,CE,FG,AC,EF}, total 1+2+2+2+3+5=15; DF=6 and EG=7 stay unused.

After rebuilding the trace and the changed-weight variant, use GATE Guidance by Sanchit Sir for a structured route through the wider Algorithms syllabus.