- #1
L4N0
- 4
- 0
Homework Statement
Suppose a weighted connected graph G = (V,E) has n edges.
Describe an algorithm to find a Minimum Spanning Tree of G in O(n) time. Prove the correctness of your answer. (Here n = |V |).
Homework Equations
I know about DFS, BFS, Prims algorithm
The Attempt at a Solution
I was thinking of running something similar to Breadth first search (BFS).
Keep track of edges part of MST (call it EMST), and vertices part of MST (call it VMST)
--
-select a vertex
-look at all adjacent edges and find the one with minimum weight (by keeping a variable 'min' and updating it as we loop)
-put the min edge in EMST, so we don't look at it again
-put the current vertex and the other vertex connected by the edge both in VMST
-then for all vertices in VMST repeat the procedure (so look at all of their vertices and find min to add to the VMST)
--
I'm not sure if this procedure is O(n), I'm afraid it might be slower, but I can't think of a way to improve it. I'm also a bit unsure how to take advantage of n=|V|