8.7
Idea: Adding e=(u,v,w) to the tree [math]T[/math] creates a single cycle.
Let [math]f[/math] be the heaviest edge on the unique T-path between [math]u[/math] and [math]v[/math]. If [math]w < w(f)[/math] we can obtain a cheaper tree by deleting [math]f[/math] and keeping [math]e[/math]; otherwise the original [math]T[/math] is still optimal. The path (hence [math]f[/math]) can be found with one DFS/BFS, which touches every vertex at most once → [math]O(n)[/math] time.
MST-update(T, e=(u,v,w)):
visited ← {false}·n
bestEdge ← (None, weight = −∞)
function dfs(x, parent):
if x == v: return true
visited[x] ← true
for each (x,y,wx,y) in T where !visited[y]:
if dfs(y,x):
if wx,y > bestEdge.weight: bestEdge ← (x,y,wx,y)
return true
return false
dfs(u, None)
if w < bestEdge.weight:
T ← T − bestEdge + e // replace
return T // new MST
Correctness: The cycle property of MSTs says that for any cycle, the heaviest edge can be removed without increasing total weight. The cycle formed is exactly the path plus [math]e[/math]; therefore exchanging [math]f[/math] with [math]e[/math] yields the unique minimum-weight spanning tree when [math]w < w(f)[/math] and leaves the tree unchanged otherwise.
Running time: one DFS/BFS on [math]T[/math] has cost [math]O(n)[/math]; all other operations are [math]O(1)[/math]. Hence the total is [math]\Theta(n)[/math] as required.
Back to
Chapter 8
