Changeset 1584:cf4bc8d477f4 in lemon0.x for doc/quicktour.dox
 Timestamp:
 07/22/05 18:57:07 (19 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@2087
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

doc/quicktour.dox
r1580 r1584 144 144 length of wires then you might be looking for a <b>minimum spanning 145 145 tree</b> in an undirected graph. This can be found using the Kruskal 146 algorithm: the function \ref lemon::kruskal "LEMON Kruskal " does 147 this job for you. After we had a graph \c g and a cost map \c 148 edge_cost_map , the following code fragment shows an example how to get weight of the minmum spanning tree (in this first example the costs are uniform; this is of course not the case in real life applications): 146 algorithm: the function \ref lemon::kruskal "LEMON Kruskal " does this 147 job for you. 148 149 First make a graph \c g and a cost map \c 150 edge_cost_map, then make a bool edgemap \c tree_map or a vector \c 151 tree_edge_vec for the algorithm output. After calling the function it 152 gives back the weight of the minimum spanning tree and the \c tree_map or 153 the \c tree_edge_vec contains the edges of the tree. 154 155 If you want to store the edges in a bool edgemap, then use the 156 function as follows: 149 157 150 158 \dontinclude kruskal_demo.cc 151 \skip std::cout 152 \until kruskal 153 154 In the variable \c tree_map the function gives back an edge bool map, which contains the edges of the found tree. 155 156 If the costs are nonuniform, for example the cost is given by \c 157 edge_cost_map_2 , or the edges of the tree have to be given in a 158 vector, then we can give to the kruskal a vector \c tree_edge_vec , instead of 159 an edge bool map: 160 161 \skip edge_cost_map_2 162 \until edge_cost_map_2, std::back_inserter 163 164 And finally the next fragment shows how to use the functions \c makeKruskalMapInput and \c makeKruskalSequenceOutPut: 165 166 \skip makeKruskalSequenceOutput 167 \until tree_edge_vec 159 \skip Kruskal with boolmap; 160 \until std::endl 161 162 And if you rather use a vector instead of a bool map: 163 164 \skip Kruskal with vector; 165 \until std::endl 168 166 169 167 See the whole program in \ref kruskal_demo.cc.
Note: See TracChangeset
for help on using the changeset viewer.