1
$\begingroup$

I am studying Kruskal's algorithm. Is the only acceptable sorting criteria to sort edges from lowest weighted edge to greatest weighted edge? I ask this because I assume that if the algorithm used an alternative sorting criteria say, greatest to lowest, then it would not produce a MST. My reasoning is that edges with larger weights would be added first.

Any help with this concept would be greatly appreciated.

$\endgroup$
2
$\begingroup$

Yes, for Kruskal's you have to sort it in ascending order of weights, for precisely the reason that you gave.

There is, however, another algorithm, namely Reverse-Delete which is essentially the opposite of Kruskal's. You start with the original graph, and process edges in descending order of weight. Then we remove each edge while the graph is still connected.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.