Math 2.0

Combinatorics Definition

Kruskal's algorithm

Builds on GraphConnected graphCycleSpanning treeMinimum spanning treeAlgorithm

Definition

Let G=(V,E)G = (V, E) be a finite connected graph and let w ⁣:E→ℝw \colon E \to \R be a weight function on its edges. Kruskal's algorithm is the following algorithm.

  1. List the edges as e1,…,eme_1, \dots, e_m with w(e1)≤w(e2)≤⋯≤w(em)w(e_1) \le w(e_2) \le \dots \le w(e_m).
  2. Start with the empty set F=∅F = \emptyset.
  3. For i=1,…,mi = 1, \dots, m in turn, add eie_i to FF if the graph (V,F∪{ei})(V, F \cup \set{e_i}) has no cycle.

It returns FF, which is the edge set of a minimum spanning tree of GG.

Remarks

Example: let GG be the triangle on {a,b,c}\set{a, b, c} with w(ab)=1w(ab) = 1, w(bc)=2w(bc) = 2 and w(ac)=3w(ac) = 3. The algorithm adds abab and bcbc, and it rejects acac because ab,bc,acab, bc, ac form a cycle. The tree {ab,bc}\set{ab, bc} has weight 33, the least weight of a spanning tree of GG.

Non-example: if GG is not connected, no spanning tree exists. The same steps then return a minimum spanning forest, that is, a minimum spanning tree of each connected component.

Correctness follows from the cut property: a lightest edge crossing any partition of VV into two parts lies in some minimum spanning tree. With a disjoint-set (union-find) structure for the cycle test, the running time is O(mlog⁡m)O(m \log m).

Reading path

To understand this page from the ground up, read these 7 pages in order. The foundations come first.

Show the path as a graph
Algorithm, concept, no evidence levelAlgorithmconceptConnected graph, concept, no evidence levelConnected graphconceptCycle, concept, no evidence levelCycleconceptGraph, concept, no evidence levelGraphconceptMinimum spanning tree, concept, no evidence levelMinimum spanning treeconceptSpanning tree, concept, no evidence levelSpanning treeconceptKruskal's algorithm, definition, no evidence levelKruskal's algorithmdefinition
Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.
  • no evidence level
  1. Algorithm concept
  2. Connected graph concept
  3. Cycle concept
  4. Graph concept
  5. Minimum spanning tree concept
  6. Spanning tree concept
  7. Kruskal's algorithm definition

Further reading

  1. Web https://en.wikipedia.org/wiki/Kruskal%27s_algorithm
About this page
TagZQVQTP6E2K
URIm2://ZQVQTP6E2K
Kinddefinition
WritingW0 stub
MSC05C85, 05C05, 90C27
DefinesKruskal's algorithm
UsesGraph, Connected graph, Cycle, Spanning tree, Minimum spanning tree, Algorithm
Changed3 November 2026

Markdown · JSON · Edit on GitHub

What this page needs for W1

  • an inventory row: the row of the inventory that the node accounts for (0 of 1)
  • a source with a locator (0 of 1)

The writing levels say how complete the text of a page is. They do not measure its truth.

What links here

No page links to this page yet.