(This is a copy of the answer to the same question on the general StackOverflow)
There exist algorithms that can add a vertex with all its edges to a graph with a known MST in linear time, which is faster than Prim or Kruskal. Probably the most neat algorithm proposed in the paper below [1] uses just one cleverly designed DFS call. It is strange that people do not know this algorithm, although it can be explained by its date: it was proposed long before both Prim and Kruskal.
That algorithm is based on an observation that the new MST shall consist of edges that either belong to the old MST or are adjacent to the newly inserted vertex (let's denote it z as in the cited paper). Furthermore, it constructs the new MST recursively while performing a depth-first search on the old MST. So its running time is proportional to the number of edges in the old MST, plus the number of edges adjacent to z, hence O(n). The way it does it is detailed below.
- While traversing the old MST, the algorithm writes out the edges that definitely belong to the new MST.
- When exiting a vertex w, the algorithm has written out all the edges that belong to an MST of the subtree of w plus the vertex z, except its heaviest edge. The fate of this heaviest edge is to be determined later, because the subtree may be connected to the rest of the graph either via z or via some old edge - so the algorithm returns this heaviest edge from the call to DFS.
- To process a w, it starts by adding the edge wz to the graph, but as it is also the heaviest edge at that moment, it is not yet written out, but kept in a separate variable t. Then it iterates over the children of of w, if any, and runs DFS recursively on each of them. Let the current child be r, and let the DFS call on it return an edge t'. One of rw and t' has to be in the final MST - otherwise some of the vertices in the subtree of r will never get connected - so the cheapest one gets written out. The heaviest one may still survive, but first it needs to compete with t: it replaces t only if t is heavier, otherwise keeping t is better. Then the algorithm continues with the next child, or, if there are no more children, returns t.
- When the algorithm exits from the root vertex of the old MST, there is no other choice than to add the just-returned edge to the new MST, thus completing the run.
Using Python as pseudocode, the algorithm can be written down as follows:
def update_mst(w, z):
visited(w) = True
t = edge(w, z)
for r in old_mst_adjacent(w):
if not visited(r):
tt = update_mst(r, z)
rw = edge(r, w)
if cost(rw) < cost(tt):
add_to_new_mst(rw)
t = min(t, tt)
else:
add_to_new_mst(tt)
t = min(t, rw)
return t
Note that [1] uses a global variable instead of returning the heaviest edge from the recursive call, but the presented way is, I think, somewhat cleaner to the modern programmers.
[1] Francis Chin and David Houck. 1978. Algorithms for Updating Minimal Spanning Trees. J. Comput. System Sci. 16 (1978), 333–344.