Prim’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

Prim’s algorithm is another classic algorithm for finding a minimum spanning tree (MST) of an undirected weighted graph. Unlike Kruskal’s algorithm which works edge by edge, Prim’s algorithm grows the MST one vertex at a time.

Telephone Network Planning

This example applies Prim’s algorithm to the same telephone network planning problem as in the Kruskal example. The goal is to find the minimum cost way to connect all towns in a region using existing roads.

Prim’s Algorithm

Prim’s algorithm grows the minimum spanning tree one vertex at a time. The basic idea is to add vertices to the MST based on which of the remaining vertices shares an edge having minimum weight with any of the vertices already in the tree.

The algorithm proceeds as follows:

  1. Start with an arbitrary vertex as the initial tree

  2. Find the minimum weight edge connecting a vertex in the tree to a vertex outside

  3. Add that edge and vertex to the tree

  4. Repeat until all vertices are in the tree

Relationship to Dijkstra’s Algorithm

Prim’s algorithm is remarkably similar to Dijkstra’s shortest-paths algorithm. In fact, the BGL implementation of Prim’s algorithm is simply a call to Dijkstra’s algorithm, with a special choice for the distance comparison and combine functions.

The key difference:

  • Dijkstra: d[v] = min(d[u] + w(u,v), d[v]) (accumulate path weight)

  • Prim: d[v] = min(w(u,v), d[v]) (only consider edge weight)

Output Format

Prim’s algorithm outputs the MST as a predecessor map. For each vertex v in the graph, parent[v] is the parent of v in the minimum spanning tree. This representation is more compact than storing edges explicitly.

If parent[v] == v, then either v is the root of the tree or it was not in the same connected component as the rest of the vertices.

Non-Uniqueness of MSTs

Note that the MST produced by Prim’s algorithm may be slightly different from the one produced by Kruskal’s algorithm when multiple edges have the same weight. This highlights the fact that minimum spanning trees are not unique; there can be more than one MST for a particular graph (though they all have the same total weight).

NWGraph Implementation

NWGraph provides a prim function that implements Prim’s algorithm using a priority queue to efficiently select the minimum weight edge.

Listing 7 Complete source code
  1/**
  2 * @file ch6_prim.cpp
  3 *
  4 * @brief Prim's Minimum Spanning Tree Algorithm (BGL Book Chapter 6)
  5 *
  6 * This example demonstrates Prim's algorithm for finding a minimum spanning
  7 * tree of an undirected weighted graph. Unlike Kruskal's algorithm which
  8 * works with edges, Prim's algorithm grows the MST from a starting vertex.
  9 *
 10 * Both algorithms produce the same MST (or one of equal weight if there
 11 * are ties), but Prim's is often more efficient for dense graphs.
 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 <limits>
 25#include <queue>
 26#include <vector>
 27
 28#include "nwgraph/adjacency.hpp"
 29#include "nwgraph/edge_list.hpp"
 30
 31using namespace nw::graph;
 32
 33/**
 34 * @brief Simple implementation of Prim's MST algorithm
 35 *
 36 * This is a straightforward implementation similar to the BGL book's approach.
 37 * It uses a priority queue to always select the minimum weight edge connecting
 38 * a visited vertex to an unvisited vertex.
 39 *
 40 * @return Vector of predecessor vertices (the MST as a parent array)
 41 */
 42template <typename Graph, typename Weight>
 43auto prim_mst(const Graph& G, size_t source, Weight weight_fn) {
 44  size_t N = G.size();
 45
 46  std::vector<double> distance(N, std::numeric_limits<double>::max());
 47  std::vector<size_t> predecessor(N, std::numeric_limits<size_t>::max());
 48  std::vector<bool> in_mst(N, false);
 49
 50  distance[source] = 0;
 51
 52  // Priority queue: (distance, vertex)
 53  using pq_element = std::pair<double, size_t>;
 54  std::priority_queue<pq_element, std::vector<pq_element>, std::greater<pq_element>> pq;
 55  pq.push({0, source});
 56
 57  while (!pq.empty()) {
 58    auto [d, u] = pq.top();
 59    pq.pop();
 60
 61    if (in_mst[u]) continue;
 62    in_mst[u] = true;
 63
 64    // Examine all adjacent vertices
 65    for (auto&& edge : G[u]) {
 66      auto v = std::get<0>(edge);
 67      auto w = weight_fn(edge);
 68
 69      // Key difference from Dijkstra: we compare edge weight, not total path
 70      if (!in_mst[v] && w < distance[v]) {
 71        distance[v] = w;
 72        predecessor[v] = u;
 73        pq.push({distance[v], v});
 74      }
 75    }
 76  }
 77
 78  return std::make_pair(predecessor, distance);
 79}
 80
 81int main() {
 82  std::cout << "=== Prim's Minimum Spanning Tree ===" << std::endl;
 83  std::cout << "Based on BGL Book Chapter 6" << std::endl << std::endl;
 84
 85  // Create the same graph as in ch6_kruskal.cpp for comparison
 86  std::cout << "Graph: 7 vertices representing cities" << std::endl;
 87  std::cout << "Same graph as Kruskal example for comparison" << std::endl;
 88  std::cout << std::endl;
 89
 90  // For Prim's algorithm, we need an adjacency list (for efficient neighbor access)
 91  // Using undirected graph, so we add edges in both directions
 92  edge_list<directedness::undirected, double> edges(7);
 93  edges.open_for_push_back();
 94  edges.push_back(0, 1, 7.0);   // A-B
 95  edges.push_back(0, 3, 5.0);   // A-D
 96  edges.push_back(1, 2, 8.0);   // B-C
 97  edges.push_back(1, 3, 9.0);   // B-D
 98  edges.push_back(1, 4, 7.0);   // B-E
 99  edges.push_back(2, 4, 5.0);   // C-E
100  edges.push_back(3, 4, 15.0);  // D-E
101  edges.push_back(3, 5, 6.0);   // D-F
102  edges.push_back(4, 5, 8.0);   // E-F
103  edges.push_back(4, 6, 9.0);   // E-G
104  edges.push_back(5, 6, 11.0);  // F-G
105  edges.close_for_push_back();
106
107  // Build symmetric adjacency list
108  adjacency<0, double> G(edges);
109
110  std::cout << "Running Prim's algorithm from vertex 0..." << std::endl;
111  std::cout << std::endl;
112
113  auto weight_fn = [](auto&& edge) { return std::get<1>(edge); };
114  auto [predecessor, key] = prim_mst(G, 0, weight_fn);
115
116  // Display MST as predecessor tree
117  std::cout << "MST as predecessor array:" << std::endl;
118  double total_weight = 0.0;
119  for (size_t v = 0; v < G.size(); ++v) {
120    if (predecessor[v] != std::numeric_limits<size_t>::max()) {
121      std::cout << "  " << predecessor[v] << " -> " << v << " : " << key[v] << std::endl;
122      total_weight += key[v];
123    }
124  }
125
126  std::cout << std::endl;
127  std::cout << "Total MST weight: " << total_weight << std::endl;
128  std::cout << std::endl;
129
130  // Show the key (distance) for each vertex
131  std::cout << "Final key values (edge weight to MST):" << std::endl;
132  for (size_t v = 0; v < G.size(); ++v) {
133    std::cout << "  Vertex " << v << ": ";
134    if (key[v] == std::numeric_limits<double>::max()) {
135      std::cout << "inf (unreachable)";
136    } else {
137      std::cout << key[v];
138    }
139    std::cout << std::endl;
140  }
141
142  std::cout << std::endl;
143  std::cout << "Note: Both Kruskal and Prim produce the same MST weight (39.0)" << std::endl;
144  std::cout << "Prim grows the tree from a single vertex, Kruskal merges forests." << std::endl;
145
146  return 0;
147}

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_prim

Then run the example:

./examples/bgl-book/ch6_prim

The program computes the MST starting from an arbitrary vertex and outputs the predecessor map representing the tree.

Sample Output

Telephone Network MST (Prim's Algorithm)

Starting vertex: Nobel

MST edges (via predecessor map):
Parry Sound's parent: Nobel (3 miles)
McKellar's parent: Parry Sound (9 miles)
...

Total wire required: 145 miles

Key NWGraph Features Demonstrated

  • Priority queue traversal: Similar to Dijkstra’s algorithm

  • Predecessor maps: Recording the MST structure

  • Weighted undirected graphs: Road networks with distances

  • Greedy algorithm: Always selecting the minimum weight edge

References

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

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

See Also