Log In
1 vote

suppose that a graph G has MST already computed. How quickly can we update the MST if we add a new vertex and incident edges to it.

I know for the best case scenario when a single edge is incident from the newly added vertex. but for the worst case, when the newly added vertex has an edge incident to the every other vertex in the MST, then i'm getting confused as how should we proceed?

there are two solutions i've got online, which i'm attaching here for reference.

solution 1:

If there is only one edge, just add this edge.

If there are k(k > 1) edges, then we need to remmove k-1 edges. We can find cycles by Union-Find and remove the weightest edge in an union. This algorithm need (k-1) passes.

solution 2:

We first add all the edges to the new vertex. Then, we preform a DFS rooted at that vertex. As we go down, we keep track of the largest weight edge seen so far since each vertex above us in the DFS. We know from exercise 23.3-6 that in a directed graph, we don’t need to consider cross or forward edges. Every cycle that we detect will then be formed by a back edge. So, we just remove the edge of greatest weight seen since we were at the vertex that the back edge is going to. Then, we’ll keep going until we’ve removed one less than the degree of the vertex we added many edges. This will end up being linear time since we can reuse part of the DFS that we had already computed before detecting each cycle.


closed as a duplicate of: adding vertex to spanning tree
in Algorithms
closed by
U mean if it is a complete graph, then what will be scenario


But first u need to consider if all edges of graph contains distinct edge weight or not

If all edges have distinct edge weight, then only 1 MST will be possible there too


Ma'am, i guess what i'm trying to say is unclear.

i'm saying that, suppose M is my MST. now a vertex v is added to the MST, and there is an edge from vertex v to every other vertex in the MST M,..., then what will be the scenario. As we can see that this is not the case of complete graph. (this is because, we are adding vertex and edged to the MST not the original graph)
then it will be no more an mst.

because, then it will definitely form a cycle
Ma'am this is what the question is... How quickly can we update the MST..

this is ur solution I think

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 O(1).

The most usual way to add an edge e=(u, v) into a MST T is:

  • Run a BFS in T from u to v to detect the edge with maximum value in that path. (O(|V|))
  • 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. (O(1)).

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.

if more problem, plz tell me


yes Ma'am, problem.

in the link you have attached, the question is that a single edge is added to the graph G. but in the question i've asked, they are adding a vertex and the edges incident from it to the MST.

both the questions are different in the number of vertices and edges added.

if we are adding a single edge to the graph, solution will be simpler in the sense that we will simply add the new edge to the MST and then apply BFS or DFS for the cycle and removing heaviest edge,

but when we are adding arbitrary number of edges(we don't know how many), then the solution would be slightly complex i think. that's where i'm stuck.

@srestha Ma'am,

this question was already asked.. i just saw.

in the 1st answer, it is given that complexity will be O(VlogV). 

u mean fibonacci heap can do this.


generic algo will be applied here

while A does not form a spanning tree
find an edge (u,v)  that is safe for A
A = AU(u,v) 
return A

because kruskal,primes already do it by greedy algo

but in case of tie what we need to do , can done by grneric algo only


is it visible?
Yes ma'am it's visible.

I'm just looking over the algorithm page you shared.
But I'm not getting why apply generic algorithm.
if there is a tie

how u evaluate it?
We can chose any of the edge.
no, I think u must have to choose safe edge one


Related questions

2 votes
3 answers
Consider the following graph and Assume node ‘P’ as the starting vertex for Prim’s algorithm. Which of the following can be the correct order of edges in which they are added to construct Minimum Spanning Tree (MST)? P-Q, P-X, X-V, V-U, U-R, R-S, R-W, S-T P-Q, P-X, X-V, V-U, U-R, R-W, R-S, S-T P-Q, Q-R, R-W, W-V, V-X, V-U, R-S, S-T P-Q, Q-R, R-W, R-S, V-X, V-U, W-V, S-T
asked Nov 17, 2017 in Algorithms Parshu gate 958 views
1 vote
0 answers
Here the graph that I was trying to find MST using algo in cormen.(If you need algo to ask, I supposed you have it) Algorithms uses min queue in process, my dobut is when it came to choice b/w vertex 'c' and 'd' as at that time both will have 8 has key ... we get wrong answer, so prism deal with this case? If you need algo I will given you, or just please refer chapter 23 cormen prim's algorithm.
asked Aug 5, 2017 in Algorithms bhuv 471 views
3 votes
2 answers
It may be the case that "Kruskal's Algorithm may not maintain connectivity while Prim's algorithm always does that" ? Any example which favours this ?
asked Jan 24, 2017 in Algorithms Kapil 2.2k views
0 votes
0 answers
Here it is mentioned as a queue and not a priority queue ,what would be the answer ?
asked Jan 5, 2017 in Algorithms Harsh181996 104 views