Jump to content

Minimum Spanning Tree

Nomadyb
in Computer Science

Featured Replies

Explain the shortest way to create a new MST that occurs when adding a new node and Edge weight, without touching the nodes and edge weights of the existing MST that we have

3 hours ago, Nomadyb said:

Explain the shortest way to create a new MST that occurs when adding a new node and Edge weight, without touching the nodes and edge weights of the existing MST that we have

The question is slightly ambiguous. A MST is per definition the "shortest way" to connect all nodes. What does "without touching" mean? The algorithm must be able to visit edges in the existing MST and if required remove one edge (the new edge or some other edge) otherwise there will be a cycle in the graph and hence not a tree. 

Note that the question seems like a typical homework task and if that is the case this forums has specific rules that apply.

Please sign in to comment

You will be able to leave a comment after signing in

Sign In Now
https://www.scienceforums.net/topic/124169-minimum-spanning-tree/
Go to topic listing

Important Information

We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.

Configure browser push notifications
Chrome (Android)
  1. Tap the lock icon next to the address bar.
  2. Tap Permissions → Notifications.
  3. Adjust your preference.
Chrome (Desktop)
  1. Click the padlock icon in the address bar.
  2. Select Site settings.
  3. Find Notifications and adjust your preference.