- #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|