I have a possible solution for the following question, but not sure if correct:
Assume we have already found a minimum spanning tree
T for a weighted, undirected graph
G = (V,E). We would like to be able to efficiently update
G be altered slightly.
An edge is added to
G to produce a new graph. Give an algorithm that uses
T to find a minimum spanning tree for the new graph in
for each vertex do
if smallest edge not in T then
replace this edge with existing edge in T
I do not have much experience in writing pseudocode, so my algorithm might be over-simplified or incorrect. Please correct me if I am wrong. Thanks!
Best How To :
Don't know if your algorithm is correct, but it doesn't seem
O(|V|) at least, because getting the "smallest edge not in T" of a vertex cannot be done in
The most usual way to add an edge
e=(u, v) into a MST
- Run a BFS in
v to detect the edge with maximum value in that path. (
- If that edge's weight is greater than the weight of the edge you're trying to add, remove that old edge and add the new one. Otherwise, do nothing, because the new edge would not improve the MST. (
The rationale behind this solution is that simply adding the edge into
T would create exactly one cycle, and to restore the MST property you have to remove the edge with maximum value from that cycle.