Kruskal’s Minimum Spanning Tree Algorithm (BGL Book Chapter 6)

Based on “The Boost Graph Library” by Jeremy Siek, Lie-Quan Lee, and Andrew Lumsdaine

Overview

Given an undirected, weighted graph, a minimum spanning tree (MST) is a subset of edges that connects all the vertices together, without any cycles, with the minimum possible total edge weight.

More precisely, for a graph G = (V, E), the minimum spanning tree problem is to find an acyclic subset T of E that connects all the vertices in V and whose total weight is minimized.

Telephone Network Planning

Suppose that you are responsible for setting up the telephone lines for a remote region. The region consists of several towns and a network of roads. Setting up a telephone line requires access for the trucks, and hence, a road alongside the route for the line.

Your budget is quite small, so building new roads is out of the question and the telephone lines will have to go in along existing roads. Also, you would like to minimize the total length of wire required to connect all the towns in the region.

The telephone network planning problem is a classic application of minimum spanning trees.

Kruskal’s Algorithm

Kruskal’s algorithm starts with each vertex in a tree by itself and with no edges in the set T (which will become the minimum spanning tree). The algorithm then:

  1. Sort edges by weight in non-decreasing order

  2. Examine each edge in sorted order

  3. If the edge connects two vertices in different trees, merge the trees and add the edge to T

  4. Continue until all edges have been examined

When finished, T will span the graph (assuming it’s connected) and be a minimum spanning tree.

The key data structure used by Kruskal’s algorithm is the disjoint-set (also called union-find), which efficiently tracks which vertices belong to the same tree and supports merging trees.

Comparison with Prim’s Algorithm

Feature

Kruskal’s

Prim’s

Approach

Edge-centric

Vertex-centric

Data structure

Disjoint-set (union-find)

Priority queue

Better for

Sparse graphs

Dense graphs

Time complexity

O(E log E)

O(E log V) with heap

Note that minimum spanning trees are not unique; there can be more than one MST for a particular graph if multiple edges have the same weight.

NWGraph Implementation

NWGraph provides a kruskal function that implements Kruskal’s algorithm using the disjoint-set data structure.

Listing 6 Complete source code
  1/**
  2 * @file ch6_kruskal.cpp
  3 *
  4 * @brief Kruskal's Minimum Spanning Tree Algorithm (BGL Book Chapter 6)
  5 *
  6 * This example demonstrates Kruskal's algorithm for finding a minimum spanning
  7 * tree of an undirected weighted graph. The algorithm works by sorting edges
  8 * by weight and adding them to the tree if they don't create a cycle.
  9 *
 10 * Application: Network design - finding the minimum cost way to connect all
 11 * nodes in a network (e.g., laying cable between cities).
 12 *
 13 * @copyright SPDX-FileCopyrightText: 2022 Battelle Memorial Institute
 14 * @copyright SPDX-FileCopyrightText: 2022 University of Washington
 15 *
 16 * SPDX-License-Identifier: BSD-3-Clause
 17 *
 18 * @authors
 19 *   Andrew Lumsdaine
 20 *
 21 */
 22
 23#include <iostream>
 24#include <numeric>
 25#include <vector>
 26
 27#include "nwgraph/algorithms/kruskal.hpp"
 28#include "nwgraph/edge_list.hpp"
 29
 30using namespace nw::graph;
 31
 32int main() {
 33  std::cout << "=== Kruskal's Minimum Spanning Tree ===" << std::endl;
 34  std::cout << "Based on BGL Book Chapter 6" << std::endl << std::endl;
 35
 36  // Create a weighted undirected graph
 37  // This represents a network where we want to find the minimum cost
 38  // to connect all nodes.
 39  //
 40  //     1---7---2
 41  //    /|      /|\
 42  //   5 9     8 7 5
 43  //  /  |    /  |  \
 44  // 0   |   /   |   5
 45  //  \  |  /    |  /
 46  //   5 15     9  11
 47  //    \|/      |/
 48  //     4---6---6
 49  //
 50  // Vertex names (for reference):
 51  // 0=A, 1=B, 2=C, 3=D, 4=E, 5=F, 6=G
 52
 53  std::cout << "Graph: 7 vertices representing cities" << std::endl;
 54  std::cout << "Edges represent possible cable routes with costs" << std::endl;
 55  std::cout << std::endl;
 56
 57  edge_list<directedness::undirected, double> edges(7);
 58  edges.open_for_push_back();
 59  edges.push_back(0, 1, 7.0);   // A-B: cost 7
 60  edges.push_back(0, 3, 5.0);   // A-D: cost 5
 61  edges.push_back(1, 2, 8.0);   // B-C: cost 8
 62  edges.push_back(1, 3, 9.0);   // B-D: cost 9
 63  edges.push_back(1, 4, 7.0);   // B-E: cost 7
 64  edges.push_back(2, 4, 5.0);   // C-E: cost 5
 65  edges.push_back(3, 4, 15.0);  // D-E: cost 15
 66  edges.push_back(3, 5, 6.0);   // D-F: cost 6
 67  edges.push_back(4, 5, 8.0);   // E-F: cost 8
 68  edges.push_back(4, 6, 9.0);   // E-G: cost 9
 69  edges.push_back(5, 6, 11.0);  // F-G: cost 11
 70  edges.close_for_push_back();
 71
 72  std::cout << "Input edges (sorted by weight for Kruskal):" << std::endl;
 73  std::vector<std::tuple<size_t, size_t, double>> sorted_edges;
 74  for (auto&& [u, v, w] : edges) {
 75    sorted_edges.push_back({u, v, w});
 76  }
 77  std::sort(sorted_edges.begin(), sorted_edges.end(),
 78            [](auto& a, auto& b) { return std::get<2>(a) < std::get<2>(b); });
 79
 80  for (auto&& [u, v, w] : sorted_edges) {
 81    std::cout << "  " << u << " -- " << v << " : " << w << std::endl;
 82  }
 83  std::cout << std::endl;
 84
 85  // Run Kruskal's algorithm
 86  auto mst = kruskal(edges);
 87
 88  // Display MST edges
 89  std::cout << "Minimum Spanning Tree edges:" << std::endl;
 90  double total_weight = 0.0;
 91  for (auto&& [u, v, w] : mst) {
 92    std::cout << "  " << u << " -- " << v << " : " << w << std::endl;
 93    total_weight += w;
 94  }
 95
 96  std::cout << std::endl;
 97  std::cout << "Total MST weight: " << total_weight << std::endl;
 98  std::cout << "Number of MST edges: " << std::distance(mst.begin(), mst.end()) << std::endl;
 99  std::cout << "(A tree with N vertices has N-1 edges)" << std::endl;
100
101  // Also demonstrate maximum spanning tree
102  std::cout << std::endl;
103  std::cout << "=== Maximum Spanning Tree ===" << std::endl;
104
105  // Recreate edge list (kruskal modifies it)
106  edge_list<directedness::undirected, double> edges2(7);
107  edges2.open_for_push_back();
108  edges2.push_back(0, 1, 7.0);
109  edges2.push_back(0, 3, 5.0);
110  edges2.push_back(1, 2, 8.0);
111  edges2.push_back(1, 3, 9.0);
112  edges2.push_back(1, 4, 7.0);
113  edges2.push_back(2, 4, 5.0);
114  edges2.push_back(3, 4, 15.0);
115  edges2.push_back(3, 5, 6.0);
116  edges2.push_back(4, 5, 8.0);
117  edges2.push_back(4, 6, 9.0);
118  edges2.push_back(5, 6, 11.0);
119  edges2.close_for_push_back();
120
121  auto max_compare = [](auto t1, auto t2) { return std::get<2>(t1) > std::get<2>(t2); };
122  auto max_st = kruskal(edges2, max_compare);
123
124  std::cout << "Maximum Spanning Tree edges:" << std::endl;
125  total_weight = 0.0;
126  for (auto&& [u, v, w] : max_st) {
127    std::cout << "  " << u << " -- " << v << " : " << w << std::endl;
128    total_weight += w;
129  }
130  std::cout << std::endl;
131  std::cout << "Total MaxST weight: " << total_weight << std::endl;
132
133  return 0;
134}

Building and Running the Example

First, configure and build the example:

# From the NWGraph root directory
mkdir -p build && cd build
cmake .. -DNWGRAPH_BUILD_EXAMPLES=ON
make ch6_kruskal

Then run the example:

./examples/bgl-book/ch6_kruskal

The program uses a sample road network and computes the minimum spanning tree, which represents the optimal layout for telephone lines.

Sample Output

Telephone Network MST (Kruskal's Algorithm)

MST edges:
Nobel -- Parry Sound (3 miles)
Novar -- Huntsville (5 miles)
Rosseau -- Sprucedale (8 miles)
...

Total wire required: 145 miles

Key NWGraph Features Demonstrated

  • Undirected weighted graphs: Road networks with distances

  • Edge sorting: Processing edges by weight

  • Disjoint-set data structure: Tracking connected components

  • Edge list output: Collecting MST edges

References

  • Cormen, Leiserson, Rivest, and Stein. Introduction to Algorithms, 4th Edition (2022), Chapter 21.1: Growing a Minimum Spanning Tree and Chapter 21.2: Kruskal’s and Prim’s Algorithms

  • Siek, Lee, and Lumsdaine. The Boost Graph Library (2002), Chapter 6.3

See Also