The Boost Graph Library: User Guide and Reference Manual

Chapter 6. Minimum-Spanning-Tree Problem

The Boost Graph Library implements two classical algorithms for solving the minimum-spanning-tree problem: Kruskal’s [23] and Prim’s [38]. The minimum-spanning-tree problem shows up in many application domains such as telephone network planning, electronic circuit layout, and data storage compression. In this chapter we apply the BGL algorithms to the telephone network planning problem.

6.1 Definitions

The minimum-spanning-tree problem is defined as follows. Given an undirected graph G = (V, E), find an acyclic subset of the edges T ⊆ E that connects all of the vertices in the graph and whose total weight is minimized. The total weight is the sum of the weight of the edges in T:

An acyclic subset of ...