Максимальный вес края в цикле в графе

Question

Я пытаюсь изменить минимальное остовное дерево, если вес края в графе, не принадлежащем MST, уменьшается. Я читаю о потоке stackoverflow, который сначала соединяет ребро с MST теперь существует только один цикл в MST и по свойству цикла край, вес которого максимален в цикле, может быть удален из MST? Как найти максимальный вес в этом цикле?

Answer 1

Пусть новый край будет добавлен между узлом я и J .There будет точно один цикл, содержащий все узлы между узлом я и J, в том числе их. Также, как и раньше, это был только один путь от узла i до j. Таким образом, вы можете использовать DFS/BFS для перемещения графика и вычисления максимального веса любого края, встречающегося в пути от i до j. Если максимальный вес меньше веса нового края, не добавляйте новый one.Else удалите предыдущий и добавьте этот. Сложность будет be O (V). Ниже приводится псевдокод, здесь ANS [к] [0], ANS [к] [1] магазин узлы таким образом, что ребро между этими узлами имеет максимальный вес, если узел источника я и назначения k и ans [k] [2] как масса этого края.

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)