<br>
<div class="gmail_quote"><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">Not really. You can use kruskal in two different ways.<br>
      * You can pass the arc cost in a Graph::ArcMap<NumType>. In this<br>
        case the algorithm sets up an std::vector<<br>
        std::pair<Arc,NumType> >, puts all the arcs and costs into it,<br>
        then _sorts_ the vector according the costs, then proceed as for<br>
        the second case.<br>
      * You can give an std::vector< std::pair<Arc,NumType> > directly<br>
        to kruskal(). Then it will _not_ sort it but will assume it is<br>
        already sorted. Thus, it picks the arcs one-by-one and adds to<br>
        the chosen arcs if it is does not form a cycle. The cost are<br>
        only used for counting the total cost of the solution and for<br>
        nothing else.<br>
<br>
Rational: Sorting is a costly operational, in fact it is costlier than<br>
finding the minimum spanning tree afterward. Therefore you have an<br>
option to skip the sorting if you have already know the right order.<br>
<div class="im"><br>
>  How can you be sure that those arcs are chosen first by Kruskal's -<br>
> since the algorithm will choose based on weight? To be safe, maybe we<br>
> should put an artificially low weight on those tree arcs in the arcs<br>
> object?<br>
<br>
</div>Yes, you can set them 0 for the 'not-on-border' arcs and to 1 for the<br>
others. But you can safely assume that kruskal() works as detailed<br>
above.<br>
<br>
The fact that the second mode does not use the cost (just sums the<br>
values) makes it possible for finding the min.cost tree according to a<br>
cost function and computing its cost according to another.<br>
<br>
Regards,<br>
Alpar<br>
<div><div></div><div class="h5"><br></div></div></blockquote><div><br><br><br>Ok. That makes sense! Thank you very much. I will try this.<br>
<br>
Matt <br></div></div>