Given 2 Algorithms for a graph G=(V,E):
One:
Two:
Do both algorithms return Minimum Spanning Tree for sure? If not I would like to see a counter example.
Both of these algorithms will find an MST if it exists. The first is Kruskal's algorithm, and the second can be proven equivalent pretty easily.
Neither of them are linear time unless the weights are constrained somehow, because they start with an O(N log N) edge sort.
Disregarding the sort, the remainder of Kruskal's algorithm is very close to linear time, because it uses a disjoint set data structure to check for connectivity.
The second algorithm doesn't have a similarly quick and straightforward implementation -- anything fast is going to be more difficult than using Kruskal's algorithm instead.