Linear Time Algorithm to Find MST?

Question

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

One:

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

Two:

Sort edges from highest to lowest weight.
Set T = E
for each edge e in the previous order, check if T{e} is connected graph. If yes, Remove e from T.
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.

Your first looks like Kruskal's algorithm; the second looks like reverse-delete. Neither is linear time. — jhnc
– jhnc, Commented Jul 31, 2022 at 8:17
What do you call linear time ? There are two independent input sizes. — user1196549
– user1196549, Commented Jul 31, 2022 at 8:41
OP, these algorithms are not linear-time in the models where computer scientists care about the open problem of finding a linear-time MST algorithm because in those models, sorting is Omega(n log n). — David Eisenstat
– David Eisenstat, Commented Jul 31, 2022 at 11:57

Matt Timmermans · Accepted Answer · 2022-07-31 13:08:14Z

1

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.

answered Jul 31, 2022 at 13:08

Matt Timmermans

60.9k3 gold badges57 silver badges106 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

user1196549 · Accepted Answer · 2022-07-31 08:45:36Z

0

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

answered Jul 31, 2022 at 8:45

user1196549

Collectives™ on Stack Overflow

Linear Time Algorithm to Find MST?

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related