Here is an excise
Suppose we are given the minimum spanning tree T of a given graph G (with n vertices and m edges) and a new edge e = (u, v) of weight w that we will add to G. Give an efficient algorithm to find the minimum spanning tree of the graph G + e. Your algorithm should run in O(n) time to receive full credit.
I have this idea:
In the MST, just find out the path between u and v. Then find the edge (along the path) with maximum weight; if the maximum weight is bigger than w, then remove that edge from the MST and add the new edge to the MST.
The tricky part is how to do this in O(n) time and it is also I get stuck.
The question is that how the MST is stored. In normal Prim's algorithm, the MST is stored as a parent array, i.e., each element is the parent of the according vertex.
So suppose the excise give me a parent array indicating the MST, how can I release the above algorithm in O(n)?
First, how can I identify the path between u and v from the parent array? I can have two ancestor arrays for u and v, then check on the common ancestor, then I can get the path, although in backwards. I think for this part, to find the common ancestor, at least I have to do it in O(n^2), right?
Then, we have the path. But we still need to find the weight of each edge along the path. Since I suppose the graph will use adjacency-list for Prim's algorithm, we have to do O(m) (m is the number of edges) to locate each weight of the edge.
...
So I don't see it is possible to do the algorithm in O(n). Am I wrong?
The idea you have is right. Note that, finding the path between u and v is O(n). I'll assume you have a parent array identifying the MST. tracking the path (for max edge) from u to v or u to root vertex should take only O(n). If you reach root vertex, just track the path from v to u or root vertex.
Now that you have the path from u -> u1 ... -> max_path_vert1 -> max_path_vert2 -> ... -> v, remove the edge max_path_vert1->max_path_vert2 (assuming this is greater than the added edge) and reverse the parents for u->...->max_path_vert1 and mark parent[u] = v.
Edit: More explanation for clarity
Note that, in MST there will be exactly one path between any pair of vertices. So, if you can trace from u->y and v->y, you have only traced through atmost n vertices. If you traced more than n vertices that means you visited a vertex twice, which will not happen in an MST. Ok, now hopefully you're convinced it's O(n) to track from u->y and v->y. Once you have these paths, you have established a path from u->v. Do you see how? I'm assuming this is an undirected graph, since finding MST for directed graph is a different concept in itself. For undirected graph, when you have a path from x->y you have a path from y-x. So, u->y->v exist. You don't even need to trace back from y->v, since weights for v->y will be same as that of y->v. Just find the edge with the maximum weight when you trace from u->y and v->y.
Now for finding edge weights in O(1); how are you storing your current weights? Adjacency list or adjacency matrix? For O(1) access, store it the way parent vertex array is stored. So, weight[v] = weight(v, parent[v]). So, you'll have O(1) access. Hope this helps.