Graph Theory → Kruskal

Example — Building the Minimum Spanning Tree

Let us apply Kruskal’s algorithm to the weighted graph below. Each edge has a weight, and the goal is to select the lightest possible edges without creating cycles.

The rule is always the same: sort the edges by weight and add only the safe ones.

Green edges are accepted into the minimum spanning tree. The dashed red edge is an example of an edge rejected because it would create a cycle.

Step 1 — Sort the edges

The algorithm begins by listing all edges in increasing order of weight:

Order: AC (1), AB (2), BD (3), CE (4), DF (5), CD (6), BC (7), CF (8), DE (9)

This step is essential because Kruskal always tries the cheapest available edge first.

But “cheapest” is not enough: the edge must also be safe, meaning that it must not close a cycle.

Step 2 — Accept the lightest safe edges

Following the sorted order:

AC (1) is accepted.
AB (2) is accepted.
BD (3) is accepted.
CE (4) is accepted.
DF (5) is accepted.

At this point, all 6 vertices are already connected. Since a tree with 6 vertices must have exactly 5 edges, the algorithm can stop.

Chosen edges: AC, AB, BD, CE, DF

Step 3 — Reject edges that create a cycle

Suppose we now try to add the edge CD (6).

It would connect two vertices that are already linked by a path: C → A → B → D. Therefore, adding CD would create a cycle.

This is exactly the kind of edge that Kruskal rejects. The tree must remain connected, but without any closed loop.

Core idea: if a new edge connects two vertices that are already connected indirectly, then it creates a cycle and must be rejected.

Final result

The minimum spanning tree found by the algorithm is:

MST: AC (1), AB (2), BD (3), CE (4), DF (5)

Its total weight is: 1 + 2 + 3 + 4 + 5 = 15.

The algorithm has connected all vertices without forming cycles and with minimum total cost.

Key intuition for Part 2

Kruskal does not try to guess the entire best tree at once. It builds the solution gradually.

At each step, it asks a very simple question: is this the lightest available edge that I can still add safely?

In the next part, we will study how to detect cycles efficiently using the Union-Find data structure.

Next step: efficient cycle detection with Union-Find.