graph kruskal_minimum_spanning_tree

Giriş
Kruskal algoritması "Disjoint set" ile gerçekleştirilebilir. Açıklaması şöyle

Path compression and other optimizations like union-by-rank should be applied any time you call the find operation on your disjoint-set forest.

One way to see this: from the perspective of Kruskal's algorithm, you just need to be able to call find and union and have them work correctly. You shouldn't need to worry about the details of how you're making find and union work correctly, just that they do. It's the responsibility of the disjoint-set forest to ensure that everything runs quickly, and so the calls to find are where you'll see the compression occurring.

İmzası şöyle

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

Örnek
Bir graph'ın weight alanlarına bakarak çalışır. Dolayısıyla weight map verilmesi gerekir. Şöyle yaparız

typedef adjacency_list<vecS, vecS, undirectedS, 
                       property<vertex_name_t,char>,
                       property<edge_weight_t,float>
                      > InternalPropGraph;


vector<edge_t> mst;
kruskal_minimum_spanning_tree(g, std::back_inserter(mst), 
                        weight_map( get(&Edge::weight, g) );