# Thread: Updated a Minimum Spanning Tree in O(V) time?

1. ## Updated a Minimum Spanning Tree in O(V) time?

I have a weighted, undirected graph. I have a Minimum Spanning Tree for that graph. One edge (u,v), with weight w, is added to the graph.

How can I update the minimum spanning tree in O(V) time?

I think of it as adding an edge to the MST, and then deciding, in O(V) time, which edge has to then be removed.

Anyone have any ideas?

2. Originally Posted by scp89
Anyone have any ideas?
Yes.

Assuming that your graph is connected (i.e. there is a path from any node to any other node), adding a new edge to the MST makes the resulting graph MST' cyclic. Hence it suffices to do a DFS on the original MST starting from u and searching for v. This will yield exactly one (u,v)-path. If its highest edge weight is larger than w((u,v))=w, remove the corresponding edge and add (u,v) to the MST, otherwise don't do anything.

Greets,
Philip

3. Thanks!

4. If this is some kind of homework, you additionally might want to argue why DFS doesn't violate the O(|V|) constraint, because all the textbooks are claiming that DFS takes time O(|V| + |E|).

Greets,
Philip

Popular pages Recent additions