Updating the minimum spanning tree when adding an edge
I have a possible solution for the following question, but not sure if it is correct:
Suppose we have already found the minimum spanning tree T
for a weighted undirected graph G = (V,E)
. We would like to be able to update efficiently T
if G
slightly modified.
An G
edge is added to the beginning of the line to create a new graph. Give an algorithm that uses T
to find the minimum spanning tree for a new graph in O(|V|)
time.
My algorithm:
for each vertex do
if smallest edge not in T then
replace this edge with existing edge in T
break
end if
end for
I don't have much experience in writing pseudocode, so my algorithm may be too simplistic or incorrect. Please correct me if I am wrong. Thank!
source to share
I don't know if your algorithm is correct, but at least it doesn't look like it O(|V|)
, because getting the "smallest edge not in T" vertex cannot be done in O(1)
.
The most common way to add an edge e=(u, v)
to an MST is T
:
- Run BFS in
T
fromu
tov
to find the edge with the maximum value along the way. (O(|V|)
) - If this edge weight is greater than the edge weight you are trying to add, remove that old edge and add a new one. Otherwise, do nothing, because the new edge will not improve the MST. (
O(1)
).
The rationale behind this decision is that simply adding an edge to T
would create exactly one cycle, and to restore the MST property, you had to remove the edge with the maximum value from this cycle.
source to share
Yes, your algorithm seems to be correct. I would amend your pseudocode to clarify that "if the smallest edge of the incident is not in T then", so your new algorithm is:
for each vertex do
if smallest incident edge not in T then
replace this edge with existing edge in T
break
end if
end for
Proof by contradiction:
There are two cases: the new edge is either in the MST or not. In the event that this is the case: suppose the algorithm does not replace an edge in T. This should mean that all edges in T are smaller than other edges that fall into the same vertex. This is a contradiction, because it means the new edge is not in MST T.
The proof for the other case is a trivially analogous proof by contradiction.
source to share