图中一个循环中边的最大权重 [英] Maximum weight of an edge in a cycle in graph

问题描述

我试图修改最小生成树，如果图中不属于MST的边的权重减少了。我在首先将边连接到MST
的stackoverflow上读取，现在只有一个周期在MST中，通过循环属性，循环中权重最大的边可以从MST中删除？如何在该周期中找到最大权重边缘？

解决方案

让新边缘添加在节点 i 和 j 。包含它们的节点 i 和 j 之间将包含所有节点。还像以前一样，它只有一条路径从节点 i 到 j 。因此，您可以使用DFS / BFS遍历图并计算从 i 到 j 的路径中出现的任何边的最大权重。如果最大权重小于的新边缘重量，请不要添加新的边缘重量。请删除前一个并添加此边框。复杂性为
为 O（V）。
以下是伪代码，这里 ans [k] [0]，ans [k] [1] 存储节点，使得这些节点之间的边缘具有最大权重节点是我和目的地 k 和 ans [k] [2] 作为该边缘的权重。

pre $ 对于所有节点
将它们标记为未访问
标记ans [节点] [2]为-1
/ * i是节点它是两个新边（i - j）的节点之一* /
在队列中推节点i Q
标记节点我访问了
，而Q不为空
将current_node指定为Q
的前面元素pop Q
当前节点的所有邻居
如果邻居未访问
标记邻居访问
指定w为最大权重如果w大于ans [邻居]
ans [邻居] [2] = w
，则边缘（current_node ---邻居）和ans [current_node]
##取决于if条件中的最大值
ans [neighbor] [0] = current_node / ans [current_node] [0]
ans [neighbor] [1] = neighbor / ans [current_node ] [1]

如果边的权重（i - j）大于ans [j] [2]
，则在Q
中推送邻居不添加新的边
else
删除边（ans [j] [0] --- ans [j] [1]）并添加边（i - j）


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?

解决方案

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)

这篇关于图中一个循环中边的最大权重的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！