Kruskal's Algorithm — Definition, Formula & Examples

Kruskal's Algorithm is a greedy method for finding a minimum spanning tree (MST) of a connected, weighted graph. It works by repeatedly selecting the cheapest available edge that does not create a cycle, until every vertex is connected.

Given a connected, undirected, weighted graph $G = (V, E, w)$ , Kruskal's Algorithm sorts all edges in $E$ by non-decreasing weight, then iteratively adds each edge to the growing forest $T$ provided it does not form a cycle in $T$ . The algorithm terminates when $|T| = |V| - 1$ , at which point $T$ is a minimum spanning tree of $G$ .

How It Works

Start by sorting every edge in the graph from smallest weight to largest. Initialize an empty edge set

T

. Go through the sorted edges one by one: if adding an edge to

T

does not create a cycle, include it; otherwise, skip it. To check for cycles efficiently, use a Union-Find (disjoint set) data structure — two vertices are in the same component if and only if they share the same root. The algorithm stops once

T

contains exactly

|V| - 1

edges, which guarantees a spanning tree.

Worked Example

Problem: Find the MST of a graph with vertices {A, B, C, D} and edges: AB = 1, AC = 4, AD = 3, BC = 2, CD = 5.

Sort edges: Order all edges by weight.

AB(1),\; BC(2),\; AD(3),\; AC(4),\; CD(5)

Add AB (weight 1): A and B are in different components. Add AB to T. Components: {A, B}, {C}, {D}.

T = \{AB\}

Add BC (weight 2): B and C are in different components. Add BC. Components: {A, B, C}, {D}.

T = \{AB,\; BC\}

Add AD (weight 3): A and D are in different components. Add AD. All vertices are now connected and |T| = 3 = |V| − 1, so stop.

T = \{AB,\; BC,\; AD\}

Answer: The MST consists of edges AB, BC, and AD with a total weight of

1 + 2 + 3 = 6

Why It Matters

Kruskal's Algorithm appears in discrete mathematics and data structures courses as a core example of greedy algorithm design. It has direct applications in network design — for instance, finding the cheapest way to lay cable connecting a set of buildings. Its time complexity of

O(|E| \log |E|)

makes it practical for sparse graphs.

Common Mistakes

Mistake: Adding an edge that creates a cycle because both endpoints already belong to the same component.

Correction: Before adding any edge, check whether its two endpoints share the same root in the Union-Find structure. If they do, skip that edge.