right?

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

right?

The Gateway to Computer Science Excellence

+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

0

U mean if it is a complete graph, then what will be scenario

right?

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

right?

right?

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

right?

0

@srestha

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)

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)

0

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

ref https://stackoverflow.com/questions/30881340/update-minimum-spanning-tree-if-edge-is-added

0

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.

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.

0

@srestha Ma'am,

this question was already asked.. i just saw.

https://gateoverflow.in/19754/adding-vertex-to-spanning-tree

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

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,737 questions

57,306 answers

198,316 comments

105,012 users