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

[scp89]

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?

[Snafuist]

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

[scp89]

Thanks!

[Snafuist]

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