Given 2 Algorithms for a graph G=(V,E):

One:

1. Sort edges from lowest to highest weight.
2. Set T = {}
3. for each edge e in the previous order, check if e Union T doesn't have any cycles. If yes, Add e to T.
4. Return T if it's a spanning Tree.

Two:

1. Sort edges from highest to lowest weight.
2. Set T = E
3. for each edge e in the previous order, check if T{e} is connected graph. If yes, Remove e from T.
4. Return T if it's a spanning Tree.

Do both algorithms return Minimum Spanning Tree for sure? If not I would like to see a counter example.

CodePudding user response：

None of the algorithms is guaranteed to build a tree because E might not be simply connected.

CodePudding user response：

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.