retagged by
18,819 views
38 votes
38 votes

Let  $G = (V, E)$ be a weighted undirected graph and let $T$ be a Minimum Spanning Tree (MST) of $G$ maintained using adjacency lists. Suppose a new weighed edge $(u, v) \in V \times V$ is added to $G$. The worst case time complexity of determining if $T$ is still an MST of the resultant graph is

  1. $\Theta (\mid E \mid + \mid V \mid) \\$
  2. $\Theta (\mid E \mid \mid V \mid) \\$
  3. $\Theta(E \mid \log \mid V \mid) \\$
  4. $\Theta( \mid V \mid)$
retagged by

5 Answers

Best answer
50 votes
50 votes

We can do this in $O(|V|)$ in the following way:

  1. Run $\textsf{BFS}$ in $T$ from $u$ to $v$ to detect the edge with maximum value in that path. $-O(|V|).$
  2. If the weight of that edge is greater than the weight of the edge you're trying to add, remove that old edge and add the new one.
  3. Otherwise, do nothing, because the new edge would not improve the $\textsf{MST}.$ $-O(1).$

The rationale behind this solution is that simply adding an edge into $T$ would create exactly one cycle, and to restore the $\textsf{MST}$ property we have to remove the edge with maximum value from that cycle.

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

edited by
22 votes
22 votes

You can imagine that there must be a cycle between the nodes u and v. Now if the newly added edge has less weight that any of the previous edge joining u and v, then you just need to replace the maximum weighted edge in that cycle with the newly added edge. In case it is not less that any of them, then no changes needs to be done. In worst case MST can have |v|-1 edges. So O(|v|) would be the answer.

option D.

Ref:- https://www.arl.wustl.edu/~jst/cse/542/exams/ex1sol.pdf

edited by
9 votes
9 votes

The key observation is that in a tree, between any two vertices there is a unique simple path. Therefore, once we add an edge between any two vertices in a tree, we will get exactly one cycle in the tree.

By cycle property of MST, we know that the maximum cost edge in a cycle in G cannot be part of our MST. Therefore, our job is to figure out the maximum cost edge in the cycle being formed. If it is the new edge, it is of no use and our MST remains same. If the maximum cost edge is not the new edge, we have to delete it and our MST will not remain the same.

Let T be the MST for the given graph G.

ALGORITHM :

  1. Find the maximum edge weight in the path from vertex u to v in T. We can use DFS for this as shown in the pseudo-code below : 
    struct node {
        int vertex;
        int weight;
    };
    
    int maxEdge;
    
    void dfs(int u, int pathMax, vector<bool>& visited,vector<node>& adjList[]) {
        visited[u] = true;
        if(u == v) {
            maxEdge = pathMax;
            return;
        }
        for(node n : adjList[u]) {
            if(visited[n.vertex] == false) {
                if(n.weight > pathMax) {
                    dfs(n.vertex, n.weight, visited, adjList);
                } else {
                    dfs(n.vertex, pathMax, visited, adjList);
                }
            }
        }
    } 
    // initial value to pathMax is INT_MIN
  2. Time Complexity for this step is O(|V| + |E|). But for a tree, |E| = |V| – 1. Therefore, the cost for this step is O(|V|).
  3. Now, once we have the maximum edge weight between u and v, we can compare this with the new edge weight. If new edge weight is greater than the maximum edge weight between u and v , then our MST remains same. In the other case, we have to delete the edge with maximum edge weight between u and v, therefore our MST changes. Cost of this step is O(1).

Therefore, total time complexity for our algorithm is O(|V|).

 

edited by
4 votes
4 votes
First of all, for distinct weighted graph we can’t do bfs.

So what we can do for this,

Already we know for minimum weight spanning tree with V vertices,we have V-1 edges.Also to traverse adjacency list ,time complexity required is O(V+E) and here for V-1 edges we have O(V) time complexity.

So while traversing adjacency list of T, we can compare the newly added weight with the weights on the node .If the newly added weight is smaller then will be change in minimum weight spanning tree otherwise not.

So we can say time complexity is O(V)
edited by
Answer:

Related questions

8 votes
8 votes
4 answers
2
Arjun asked Feb 12, 2020
9,639 views
Consider a graph $G = (V,E)$, where $V = \{v_1,v_2, \dots ,v_{100}\}$, $E = \{(v_i,v_j) \mid 1\leq i < j \leq 100\}$, and weight of the edge $(v_i,v_j)$ is $\mid i – j ...
35 votes
35 votes
9 answers
3
gatecse asked Feb 14, 2018
17,350 views
Consider the following undirected graph $G$:Choose a value for $x$ that will maximize the number of minimum weight spanning trees (MWSTs) of $G$. The number of MWSTs of $...