CoreSource checked

Kruskal's Algorithm

Builds a minimum spanning tree by adding the cheapest edges that do not create cycles.

Explore relationships Open constellationBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category: Graph Traversal
Difficulty: Intermediate
Family: Greedy Graph Algorithm
Tier: Core
Status: Verified
Review: Source Checked
Sources: 2
Formulas: 1
Relationships: 7
Code example: Ready
Visualization: Ready

Overview

Kruskal's Algorithm sorts edges by weight and uses a disjoint-set structure to decide whether each edge connects two different components.

Core Concepts

edge sortingunion-findcycle testsafe edge

Quick facts

Complexity

Runtime and memory behavior at a glance.

Best

O(E log E)

Average

O(E log E)

Worst

O(E log E)

Space

O(V)

When to Use

Use when edges can be sorted once and the graph is sparse or edge-focused.
Use when sparse graph MSTs is a central requirement.

When Not to Use

Avoid when the graph is dense and adjacency-based Prim's Algorithm is simpler for the representation.
Avoid when the graph changes faster than the traversal result can be reused.

What It Does

Sorts edges by weight
Tests whether endpoints are already connected
Adds safe edges to the growing forest

Use Cases

Sparse graph MSTs
Network design
Clustering by connectivity

Inputs

Weighted undirected graph

Outputs

Minimum spanning tree edges

Key Formulas (1)

Cycle test

accept edge (u, v) if find(u) ≠ find(v)

accept edge (u, v) if find(u) != find(v)

Adds only edges that connect two currently separate components.

Pseudocode

1.Sort all edges from lowest to highest weight
2.Create one component per node
3.For each edge, check whether its endpoints are in different components
4.Add the edge and union the components when it is safe
5.Stop after V - 1 selected edges

Canonical Example

Input: edges = A-B:1, B-C:2, A-C:4
Output: selected = [A-B, B-C]
Explanation: The cheapest edge is accepted, the next connects the remaining node, and the last would create a cycle.

Implementation Notes

Sort edges stably only if deterministic tie behavior matters for equal weights.
Use explicit node ids and keep traversal state separate from graph storage.
Keep a tiny example with expected output beside the implementation.

Common Pitfalls

Adding an edge before checking component membership can introduce cycles.
Forgetting to track visited or finalized nodes can create repeated work or cycles.
Not defining boundary, empty, or degenerate inputs before implementation.

Interactive Mechanism Walkthrough

Graph Frontier & Edge Relaxation

Show edges being considered in weight order while components merge.

Step 1 of 5: Sort all edges from lowest to highest weight

graph-traversal

Notes

Union-Find is the usual data structure for fast cycle checks.

Sources (2)

What each reference supports for this entry.

Introduction to Algorithms (CLRS)

Book

Textbook support for Kruskal's Algorithm's standard algorithm design, invariants, and complexity analysis.

Open source

The Algorithm Design Manual

Book

Algorithm catalog support for Kruskal's Algorithm's problem context, known alternatives, and practical selection tradeoffs.

Open source

Explore Next

Good next jumps from the relationship graph, ranked for useful discovery.

Open discovery Open map

Used byBoruvka's Algorithm

Graph Traversal · Core

Boruvka's Algorithm uses Kruskal's Algorithm as a subroutine, representation, or supporting idea while growing many tree components at once and repeatedly adding each component's cheapest outgoing edge.

Compare with this

Used byKruskal Maze Generation

Procedural Generation · Core

Kruskal maze generation uses Kruskal-style edge selection to carve a spanning-tree maze.

Compare with this

Used byReverse-Delete Algorithm

Graph Traversal · Core

Reverse-Delete Algorithm uses Kruskal's Algorithm as a subroutine, representation, or supporting idea while removing expensive edges when their removal does not disconnect the graph.

Compare with this

UsesUnion-Find

Data Structures · Core

Kruskal's Algorithm commonly uses Union-Find to detect cycles.

Compare with this

SpecializesMinimum Spanning Tree

Graph Traversal · Core

Kruskal's Algorithm solves the minimum spanning tree problem by sorting edges.

Compare with this