CODEWITHSUNDEEP
algorithmgraphminimum-spanning-tree
user3553836
user3553836

Reputation: 95

Maximum weight of an edge in a cycle in graph

I am trying to modify the minimum spanning tree if the weight of an edge in the graph not belonging to MST is decreased.I read on stackoverflow that first connect the edge to the MST now there is exactly one cycle in MST and by cycle property the edge whose weight is maximum in cycle can be deleted from MST? How to find the max weight edge in that cycle?

Upvotes: 2

Views: 3998

Answers (1)

advocateofnone
advocateofnone

Reputation: 2541

Let the new edge added be between node i and j.There will be exactly one cycle containing all nodes between node i and j, including them. Also as before it was a tree only one path is there from node i to j. So you can use DFS/BFS to traverse the graph and calculate the maximum weight of any edge occurring in the path from i to j.If the maximum weight is less than that of new edge weight, don't add the new one.Else remove the previous one and add this one.The complexity would be O(V). Following is the pseudo code , here ans[k][0],ans[k][1] store the nodes such that the edge between these nodes is of maximum weight if the source node is i and destination k and ans[k][2] as weight of that edge.

   for all nodes
       mark them unvisited
       mark ans[node][2] as -1
   /*i is the node which is one of the nodes of two of the new edge (i--j) */
   Push node i in queue Q
   mark node i visited
   while Q is not empty
       assign current_node as front element of Q
       pop Q
       for all neighbors of current_node
           if neighbor is unvisited
               mark neighbor visited
               assign w to be maximum of weight of edge (current_node---neighbor) and ans[current_node]
               if w is greater than ans[neighbor]
                  ans[neighbor][2] = w
                  ##Depending on which was max in the the if condition
                  ans[neighbor][0] = current_node/ans[current_node][0]
                  ans[neighbor][1] = neighbor/ans[current_node][1]

               push neighbor in Q  
if weight of edge (i--j) is greater than ans[j][2] 
     don't add the new edge
else 
     remove edge (ans[j][0]---ans[j][1]) and add edge (i--j)

Upvotes: 1

Related Questions