This documentation is being rewritten. If something looks off, please cross-check with the Boost 1.91.0 Boost.Graph docs and open an issue.

kruskal_minimum_spanning_tree

Find a minimum spanning tree in an undirected graph with weighted edges using Kruskal’s algorithm.

Complexity: O(E log E)
Defined in: <boost/graph/kruskal_min_spanning_tree.hpp>

Example

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/kruskal_min_spanning_tree.hpp>
#include <iostream>
#include <vector>

struct Road { int weight; };

int main() {
    using namespace boost;
    using Graph = adjacency_list<vecS, vecS, undirectedS, no_property, Road>;
    using Edge  = graph_traits<Graph>::edge_descriptor;

    Graph g(5);
    add_edge(0, 1, Road{2}, g);
    add_edge(0, 3, Road{1}, g);
    add_edge(1, 2, Road{3}, g);
    add_edge(1, 3, Road{2}, g);
    add_edge(2, 3, Road{5}, g);
    add_edge(2, 4, Road{4}, g);
    add_edge(3, 4, Road{6}, g);

    // Named-parameter overload: needed because the weight lives in a bundled
    // property (not the interior `edge_weight_t` tag that the 2-arg positional
    // overload would pick up).
    std::vector<Edge> mst;
    kruskal_minimum_spanning_tree(g, std::back_inserter(mst),
        weight_map(get(&Road::weight, g)));

    int total = 0;
    std::cout << "MST edges:\n";
    for (auto& e : mst) {
        int w = g[e].weight;
        std::cout << "  " << source(e, g) << " -- "
                  << target(e, g) << " (weight " << w << ")\n";
        total += w;
    }
    std::cout << "Total weight: " << total << "\n";
}
MST edges:
  0 -- 3 (weight 1)
  0 -- 1 (weight 2)
  1 -- 2 (weight 3)
  2 -- 4 (weight 4)
Total weight: 10

(1) Named parameter version

template <class Graph, class OutputIterator,
          class P, class T, class R>
OutputIterator
kruskal_minimum_spanning_tree(
    Graph& g, OutputIterator tree_edges,
    const bgl_named_params<P, T, R>& params = all defaults);
Direction Parameter Description

IN

const Graph& g

An undirected graph. The graph type must be a model of Vertex List Graph and Edge List Graph.

IN

OutputIterator spanning_tree_edges

The edges of the minimum spanning tree are output to this Output Iterator.

IN

weight_map(WeightMap w_map)

The weight or "length" of each edge in the graph. The WeightMap type must be a model of Readable Property Map and its value type must be Less Than Comparable. The key type of this map needs to be the graph’s edge descriptor type.
Default: get(edge_weight, g)

UTIL

rank_map(RankMap r_map)

This is used by the disjoint sets data structure. The type RankMap must be a model of Read/Write Property Map. The vertex descriptor type of the graph needs to be usable as the key type of the rank map. The value type of the rank map must be an integer type.
Default: an iterator_property_map created from a std::vector of the integers of size num_vertices(g) and using the i_map for the index map.

UTIL

predecessor_map(PredecessorMap p_map)

This is used by the disjoint sets data structure, and is not used for storing predecessors in the spanning tree. The predecessors of the spanning tree can be obtained from the spanning tree edges output. The type PredecessorMap must be a model of Read/Write Property Map. The key type value types of the predecessor map must be the vertex descriptor type of the graph.
Default: an iterator_property_map created from a std::vector of vertex descriptors of size num_vertices(g) and using the i_map for the index map.

IN

vertex_index_map(VertexIndexMap i_map)

This maps each vertex to an integer in the range [0, num_vertices(g)). This is only necessary if the default is used for the rank or predecessor maps. The type VertexIndexMap must be a model of Readable Property Map. The value type of the map must be an integer type. The vertex descriptor type of the graph needs to be usable as the key type of the map.
Default: get(vertex_index, g)
Note: if you use this default, make sure your graph has an internal vertex_index property. For example, adjacency_list with VertexList=listS does not have an internal vertex_index property.

(2) Positional version

template <class Graph, class OutputIterator>
OutputIterator
kruskal_minimum_spanning_tree(
    const Graph& g, OutputIterator spanning_tree_edges);

Equivalent to (1) with every named parameter left at its default. Internally calls get(edge_weight, g) and get(vertex_index, g), so the graph must have both interior properties (this is automatic for adjacency_list with vecS vertex storage, but you must declare vertex_index_t when using listS / setS).

If you need to supply a weight map or a custom disjoint-sets backing, use overload (1).

Direction Parameter Description

IN

const Graph& g

Same concept requirements as (1).

IN

OutputIterator spanning_tree_edges

Same as (1).

Description

The kruskal_minimum_spanning_tree() function find a minimum spanning tree (MST) in an undirected graph with weighted edges. A MST is a set of edges that connects all the vertices in the graph where the total weight of the edges in the tree is minimized. For more details, see section Minimum Spanning Tree Problem. The edges in the MST are output to the tree_edges output iterator. This function uses Kruskal’s algorithm to compute the MST [14,5,22,12].

Kruskal’s algorithm starts with each vertex in a tree by itself, and with no edges in the minimum spanning tree T. The algorithm then examines each edge in the graph in order of increasing edge weight. If an edge connects two vertices in different trees the algorithm merges the two trees into a single tree and adds the edge to T. We use the "union by rank" and "path compression" heuristics to provide fast implementations of the disjoint set operations (MAKE-SET, FIND-SET, and UNION-SET). The algorithm is as follows:

KRUSKAL-MST(G, w)
  T := O
  for each vertex u in V
    MAKE-SET(DS, u)
  end for
  for each edge (u,v) in E in order of nondecreasing weight
    if FIND-SET(DS, u) != FIND-SET(DS, v)
      UNION-SET(DS, u, v)
      T := T U {(u,v)}
  end for
  return T

Example

The file examples/kruskal-example.cpp contains an example of using Kruskal’s algorithm.

Edit this Page