CODEWITHSUNDEEP
c++algorithmboost
Tryer
Tryer

Reputation: 4090

Boost -- Kruskal minimum spanning tree -- guarantee of returning edges in ascending order of weights

Consider the algorithm's description provided here.

The algorithm sorts the provided edges in ascending order and processes them in this order. The code example provided on boost website gives an example of calling the algorithm via the call:

std::vector< Edge > spanning_tree;
kruskal_minimum_spanning_tree(g, std::back_inserter(spanning_tree));

After running the algorithm, the edges of the MST are accessible via:

std::cout << "Print the edges in the MST:" << std::endl;
for (std::vector< Edge >::iterator ei = spanning_tree.begin();ei != spanning_tree.end();++ei){
    std::cout << source(*ei, g) << " <--> " << target(*ei, g)<<" with weight of " << weight[*ei] << std::endl;
}

Is it guaranteed that the edges of the MST returned back in spanning_tree are stored in ascending order of the edge weights?

Upvotes: 2

Views: 142

Answers (1)

subspring
subspring

Reputation: 700

When we trace the code, we see that we pass a vector of edges called "spanning_tree" to the algorithm, if you check the output iterator (in the boost/graph/kruskal_min_spanning_tree.hpp header file), then you find that edges are added to it in the ordered that they were processed in, and since in Kruskal's algorithm we should process edges in ascending order then it is guaranteed that the returned vector contains edges sorted in ascending order.

Upvotes: 2

Related Questions