...one of the most highly
regarded and expertly designed C++ library projects in the
world.

— Herb Sutter and Andrei
Alexandrescu, C++
Coding Standards

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);

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 [18,8,27,15].

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 := Øforeach vertexu in VMAKE-SET(DS,u)end forforeach edge(u,v) in Ein order of nondecreasing weightifFIND-SET(DS,u) != FIND-SET(DS,v) UNION-SET(DS,u,v)T := T U {(u,v)}end forreturnT

`boost/graph/kruskal_min_spanning_tree.hpp`

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

Python: The parameter is namedgraph.

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

Python: This parameter is not used in Python. Instead, a Pythonlistcontaining all of the spanning tree edges is returned.

The weight or ``length'' of each edge in the graph. TheUTIL:WeightMaptype 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)

Python: Must be anedge_double_mapfor the graph.

Python default:graph.get_edge_double_map("weight")

This is used by the disjoint sets data structure. The typeUTIL:RankMapmust 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:aniterator_property_mapcreated from astd::vectorof the integers of sizenum_vertices(g)and using thei_mapfor the index map.

Python: Unsupported parameter.

This is used by the disjoint sets data structure, and isIN:notused for storing predecessors in the spanning tree. The predecessors of the spanning tree can be obtained from the spanning tree edges output. The typePredecessorMapmust 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:aniterator_property_mapcreated from astd::vectorof vertex descriptors of sizenum_vertices(g)and using thei_mapfor the index map.

Python: Unsupported parameter.

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 typeVertexIndexMapmust 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)

Python: Unsupported parameter.

The time complexity is *O(E log E)*

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

Copyright © 2000-2001 | Jeremy Siek, Indiana University (jsiek@osl.iu.edu) |