Skip to content

Minimum spanning trees

Part 2 · Trees and paths · Chapter 2 · Lecture notes, volume 2 (PDF) · Exercises: Spanning trees · App: Minimum spanning trees: Kruskal and Prim

  • 2.1 The minimum spanning tree problem

    Open

  • 2.2 Cuts and cycles

    Open

  • 2.3 The cut property and the cycle property

    Open

  • 2.4 The generic greedy algorithm

    Open

  • 2.5 Kruskal's algorithm

    Kruskal's algorithm on the reference graph

    Open

  • 2.6 Prim's algorithm

    Open

  • 2.7 Uniqueness of the minimum spanning tree

    Weights with ties

    Open

Prerequisites

  • The chapter «Graphs»: paths and cycles, connected components, the characterizations of a tree and the fundamental cycles.

  • The \(O(\cdot)\) notation for the running time of an algorithm, and sorting \(m\) numbers in \(O(m\log m)\) time.

Objectives

At the end of this chapter you will be able to:

  • state the minimum spanning tree problem and recognize it in applications;

  • prove the cut property and the cycle property, and use them to certify that a spanning tree is optimal;

  • run the algorithms of Kruskal and of Prim, prove that they are correct and analyse their running time;

  • decide whether the minimum spanning tree is unique, and find the edges that belong to every optimal tree.

Next: 2.1 The minimum spanning tree problem

Exercises on this chapter: Spanning trees

In the interactive lab: Minimum spanning trees: Kruskal and Prim.