how to find MST after add new node?

Question

How we find MST (Minimum Spanning Tree) after add new node or change distance of ways?

I need help to solve this. Can anybody help me?

Thanks.

evgeny · Accepted Answer · 2011-05-25 11:45:13Z

4

When adding new edges:

You will need to perform a graph traversal, the easiest is DFS for this, from one of the sides of the modified/new edge. If you can back to a node you were to before, you have a cycle.

In that cycle, you will need to remove the largest edge. You will get a tree again, and it is the minimal spanning one.

If you are changing edge weights, you will need to:

Disconnect the graph into 2 components, A and B, by temporarily removing the new edge.
If the new edge has a smaller weight than before, you can put it back in. Otherwise:
Iterate through edges that you have processed before, and check if they join A to B.
Pick the smallest edge from those, and connect the components using that edge.

Again, you get a new minimal spanning tree.

Overall, this is O(V+E), times a small factor of inverse Ackermann.

answered May 25, 2011 at 11:45

evgeny

2,58417 silver badges27 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

richardaum Over a year ago

What ensures that this new tree (when adding new edges) still is a minimal spanning tree?

richardaum Over a year ago

Is there any linear way to add a node (with how many edges it can)?

Collectives™ on Stack Overflow

how to find MST after add new node?

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related