equal
deleted
inserted
replaced
20 #define LEMON_KRUSKAL_H |
20 #define LEMON_KRUSKAL_H |
21 |
21 |
22 #include <algorithm> |
22 #include <algorithm> |
23 #include <vector> |
23 #include <vector> |
24 #include <lemon/unionfind.h> |
24 #include <lemon/unionfind.h> |
25 // #include <lemon/graph_utils.h> |
|
26 #include <lemon/maps.h> |
25 #include <lemon/maps.h> |
27 |
26 |
28 // #include <lemon/radix_sort.h> |
27 #include <lemon/core.h> |
29 |
|
30 #include <lemon/bits/utility.h> |
|
31 #include <lemon/bits/traits.h> |
28 #include <lemon/bits/traits.h> |
32 |
29 |
33 ///\ingroup spantree |
30 ///\ingroup spantree |
34 ///\file |
31 ///\file |
35 ///\brief Kruskal's algorithm to compute a minimum cost spanning tree |
32 ///\brief Kruskal's algorithm to compute a minimum cost spanning tree |
298 /// kruskal(g,cost,std::back_inserter(tree)); |
295 /// kruskal(g,cost,std::back_inserter(tree)); |
299 ///\endcode |
296 ///\endcode |
300 /// |
297 /// |
301 /// \return The total cost of the found spanning tree. |
298 /// \return The total cost of the found spanning tree. |
302 /// |
299 /// |
303 /// \note If the input graph is not (weakly) connected, a spanning |
300 /// \note If the input graph is not (weakly) connected, a spanning |
304 /// forest is calculated instead of a spanning tree. |
301 /// forest is calculated instead of a spanning tree. |
305 |
302 |
306 #ifdef DOXYGEN |
303 #ifdef DOXYGEN |
307 template <class Graph, class In, class Out> |
304 template <class Graph, class In, class Out> |
308 Value kruskal(GR const& g, const In& in, Out& out) |
305 Value kruskal(GR const& g, const In& in, Out& out) |