# Changeset 47:c09d90659170 in lemon-tutorial for undir_graphs.dox

Ignore:
Timestamp:
02/22/10 01:59:50 (11 years ago)
Branch:
default
Phase:
public
Message:

Write a subsection about Kruskal algorithm

File:
1 edited

Unmodified
Removed
• ## undir_graphs.dox

 r46 [SEC]sec_undir_graph_algs[SEC] Undirected Graph Algorihtms \todo This subsection is under construction. If you would like to design an electric network minimizing the total length of wires, then you might be looking for a minimum spanning tree in an undirected graph. This can be found using the \ref kruskal() "Kruskal" algorithm. See \ref spantree for the minimum spanning tree algorithms and \ref matching for matching algorithms. Let us suppose that the network is stored in a \ref ListGraph object \c g with a cost map \c cost. We create a \c bool valued edge map \c tree_map or a vector \c tree_vector for stroing the tree that is found by the algorithm. After that, we could call the \ref kruskal() function. It gives back the weight of the minimum spanning tree and \c tree_map or \c tree_vector will contain the found spanning tree. If you want to store the arcs in a \c bool valued edge map, then you can use the function as follows. \code // Kruskal algorithm with edge map ListGraph::EdgeMap tree_map(g); std::cout << "The weight of the minimum spanning tree is " << kruskal(g, cost_map, tree_map) << std::endl; // Print the results std::cout << "Edges of the tree: " << std::endl; for (ListGraph::EdgeIt e(g); e != INVALID; ++e) { if (!tree_map[e]) continue; std::cout << "(" << g.id(g.u(e)) << ", " << g.id(g.v(e)) << ")\n"; } \endcode If you would like to store the edges in a standard container, you can do it like this. \code // Kruskal algorithm with edge vector std::vector tree_vector; std::cout << "The weight of the minimum spanning tree is " << kruskal(g, cost_map, tree_vector) << std::endl; // Print the results std::cout << "Edges of the tree: " << std::endl; for (unsigned i = 0; i != tree_vector.size(); ++i) { Edge e = tree_vector[i]; std::cout << "(" << g.id(g.u(e)) << ", " << g.id(g.v(e)) << ")\n"; } \endcode \todo \ref matching "matching algorithms". [TRAILER]
Note: See TracChangeset for help on using the changeset viewer.