Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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.
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.
