1<HTML> 2<!-- 3 Copyright (c) Jeremy Siek 2000 4 5 Distributed under the Boost Software License, Version 1.0. 6 (See accompanying file LICENSE_1_0.txt or copy at 7 http://www.boost.org/LICENSE_1_0.txt) 8 --> 9<Head> 10<Title>Boost Graph Library: Kruskal Minimum Spanning Tree</Title> 11<BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b" 12 ALINK="#ff0000"> 13<IMG SRC="../../../boost.png" 14 ALT="C++ Boost" width="277" height="86"> 15 16<BR Clear> 17 18 19<H1><A NAME="sec:kruskal"> 20<img src="figs/python.gif" alt="(Python)"/> 21<TT>kruskal_minimum_spanning_tree</TT> 22</H1> 23 24<PRE> 25template <class Graph, class OutputIterator, class P, class T, class R> 26OutputIterator 27kruskal_minimum_spanning_tree(Graph& g, OutputIterator tree_edges, 28 const bgl_named_params<P, T, R>& params = <i>all defaults</i>); 29</PRE> 30 31<P> 32The <tt>kruskal_minimum_spanning_tree()</tt> function find a minimum 33spanning tree (MST) in an undirected graph with weighted edges. A MST is a 34set of edges that connects all the vertices in the graph where the 35total weight of the edges in the tree is minimized. For more details, 36see section <a 37href="graph_theory_review.html#sec:minimum-spanning-tree">Minimum 38Spanning Tree Problem</a>. The edges in the MST are output to the 39<tt>tree_edges</tt> output iterator. This function uses Kruskal's 40algorithm to compute the MST [<A 41HREF="bibliography.html#kruskal56">18</A>,<A 42HREF="bibliography.html#clr90">8</A>,<A 43HREF="bibliography.html#tarjan83:_data_struct_network_algo">27</A>,<A 44HREF="bibliography.html#graham85">15</A>]. 45</p> 46<p> 47Kruskal's algorithm starts with each vertex in a tree by itself, and 48with no edges in the minimum spanning tree <i>T</i>. The algorithm 49then examines each edge in the graph in order of increasing edge 50weight. If an edge connects two vertices in different trees the 51algorithm merges the two trees into a single tree and adds the edge to 52<i>T</i>. We use the ``union by rank'' and ``path compression'' 53heuristics to provide fast implementations of the disjoint set 54operations (<tt>MAKE-SET</tt>, <tt>FIND-SET</tt>, and 55<tt>UNION-SET</tt>). The algorithm is as follows: 56</p> 57 58<pre> 59KRUSKAL-MST(<i>G</i>, <i>w</i>) 60 <i>T := Ø</i> 61 <b>for</b> each vertex <i>u in V</i> 62 MAKE-SET(<i>DS</i>, <i>u</i>) 63 <b>end for</b> 64 <b>for</b> each edge <i>(u,v) in E</i> in order of nondecreasing weight 65 <b>if</b> FIND-SET(<i>DS</i>, <i>u</i>) != FIND-SET(<i>DS</i>, <i>v</i>) 66 UNION-SET(<i>DS</i>, <i>u</i>, <i>v</i>) 67 <i>T := T U {(u,v)}</i> 68 <b>end for</b> 69 <b>return</b> <i>T</i> 70</pre> 71 72 73<H3>Where Defined</H3> 74 75<P> 76<a href="../../../boost/graph/kruskal_min_spanning_tree.hpp"><TT>boost/graph/kruskal_min_spanning_tree.hpp</TT></a> 77 78<P> 79 80<h3>Parameters</h3> 81 82IN: <tt>const Graph& g</tt> 83<blockquote> 84 An undirected graph. The graph type must be a model of 85 <a href="./VertexListGraph.html">Vertex List Graph</a> 86 and <a href="./EdgeListGraph.html">Edge List Graph</a>.<br> 87 88 <b>Python</b>: The parameter is named <tt>graph</tt>. 89</blockquote> 90 91IN: <tt>OutputIterator spanning_tree_edges</tt> 92<blockquote> 93 The edges of the minimum spanning tree are output to this <a 94 href="http://www.boost.org/sgi/stl/OutputIterator.html">Output 95 Iterator</a>.<br> 96 97 <b>Python</b>: This parameter is not used in Python. Instead, a 98 Python <tt>list</tt> containing all of the spanning tree edges is 99 returned. 100</blockquote> 101 102 103<h3>Named Parameters</h3> 104 105IN: <tt>weight_map(WeightMap w_map)</tt> 106<blockquote> 107The weight or ``length'' of 108 each edge in the graph. The <tt>WeightMap</tt> type must be a model 109 of <a href="../../property_map/doc/ReadablePropertyMap.html">Readable 110 Property Map</a> and its value type must be <a 111 href="http://www.boost.org/sgi/stl/LessThanComparable.html">Less Than 112 Comparable</a>. The key type of this map needs to be the graph's 113 edge descriptor type.<br> 114 <b>Default:</b> <tt>get(edge_weight, g)</tt><br> 115 <b>Python</b>: Must be an <tt>edge_double_map</tt> for the graph.<br> 116 <b>Python default</b>: <tt>graph.get_edge_double_map("weight")</tt> 117</blockquote> 118 119UTIL: <tt>rank_map(RankMap r_map)</tt> 120<blockquote> 121 This is used by the disjoint sets data structure. 122 The type <tt>RankMap</tt> must be a model of <a 123 href="../../property_map/doc/ReadWritePropertyMap.html">Read/Write 124 Property Map</a>. The vertex descriptor type of the graph needs to 125 be usable as the key type of the rank map. The value type of the 126 rank map must be an integer type.<br> 127 <b>Default:</b> an <a 128 href="../../property_map/doc/iterator_property_map.html"> 129 <tt>iterator_property_map</tt></a> created from a 130 <tt>std::vector</tt> of the integers of size 131 <tt>num_vertices(g)</tt> and using the <tt>i_map</tt> for the index 132 map.<br> 133 134 <b>Python</b>: Unsupported parameter. 135</blockquote> 136 137UTIL: <tt>predecessor_map(PredecessorMap p_map)</tt> 138<blockquote> 139 This is used by the disjoint sets data structure, and is <b>not</b> 140 used for storing predecessors in the spanning tree. The predecessors 141 of the spanning tree can be obtained from the spanning tree edges 142 output. The type <tt>PredecessorMap</tt> must be a model of <a 143 href="../../property_map/doc/ReadWritePropertyMap.html">Read/Write 144 Property Map</a>. The key type value types of the predecessor map 145 must be the vertex descriptor type of the graph. <br> 146 <b>Default:</b> an <a 147 href="../../property_map/doc/iterator_property_map.html"> 148 <tt>iterator_property_map</tt></a> created from a 149 <tt>std::vector</tt> of vertex descriptors of size 150 <tt>num_vertices(g)</tt> and using the <tt>i_map</tt> for the index 151 map.<br> 152 153 <b>Python</b>: Unsupported parameter. 154</blockquote> 155 156IN: <tt>vertex_index_map(VertexIndexMap i_map)</tt> 157<blockquote> 158 This maps each vertex to an integer in the range <tt>[0, 159 num_vertices(g))</tt>. This is only necessary if the default is used 160 for the rank or predecessor maps. The type <tt>VertexIndexMap</tt> 161 must be a model of <a 162 href="../../property_map/doc/ReadablePropertyMap.html">Readable Property 163 Map</a>. The value type of the map must be an integer type. The 164 vertex descriptor type of the graph needs to be usable as the key 165 type of the map.<br> 166 <b>Default:</b> <tt>get(vertex_index, g)</tt> 167 Note: if you use this default, make sure your graph has 168 an internal <tt>vertex_index</tt> property. For example, 169 <tt>adjacency_list</tt> with <tt>VertexList=listS</tt> does 170 not have an internal <tt>vertex_index</tt> property. 171 <br> 172 173 <b>Python</b>: Unsupported parameter. 174</blockquote> 175 176 177<H3>Complexity</H3> 178 179<P> 180The time complexity is <i>O(E log E)</i> 181 182<H3>Example</H3> 183 184<P> 185The file <a 186href="../example/kruskal-example.cpp"><TT>examples/kruskal-example.cpp</TT></a> 187contains an example of using Kruskal's algorithm. 188 189 190<br> 191<HR> 192<TABLE> 193<TR valign=top> 194<TD nowrap>Copyright © 2000-2001</TD><TD> 195<A HREF="http://www.boost.org/people/jeremy_siek.htm">Jeremy Siek</A>, Indiana University (<A HREF="mailto:jsiek@osl.iu.edu">jsiek@osl.iu.edu</A>) 196</TD></TR></TABLE> 197 198</BODY> 199</HTML> 200
