图中循环中边的最大权重

Question

我正在尝试修改最小生成树，如果图中不属于 MST 的边的权重是 decreased.I 在首先将边连接到 MST 的 Whosebug 上读取现在MST中正好有一个循环，通过循环属性可以从MST中删除循环中权重最大的边吗？如何找到该循环中的最大权重边？

Answer 1

令新添加的边在节点i和j之间。节点[=之间的所有节点将恰好包含一个循环13=]i 和 j，包括它们。同样和以前一样，它是一棵树，只有一条路径从节点 i 到 j。所以可以用DFS/BFS遍历图，计算从i到j路径上出现的任意一条边的最大权值。如果最大权重小于新边权重，则不添加新的 one.Else 删除前一个并添加此 one.The 复杂度是 O(V)。以下是伪代码，这里 ans[k][0],ans[k][1] 存储节点，如果源节点，则这些节点之间的边具有最大权重是 i 和目的地 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)

图中循环中边的最大权重

Maximum weight of an edge in a cycle in graph

algorithm

graph

minimum-spanning-tree