从加权图中寻找次优最小生成树的算法
我正试图从一个加权无向图中找到跨越三的次优最小值。我知道如何使用Kruskal算法计算MST,我想用这种方法找到第二好的最小算法：
步骤：
>
对所有图形边进行排序。
使用Kruskal计算MST
从不在第一个MST中的图中获取最小权重边，并将其添加到MST中（现在MST有一个循环）
在新形成的循环中移除最大重量边
这应该是第二好的MST吧？
顺便说一句，我知道这里有一个主题，指出了一个算法，它在每个MST边之间迭代，并在图上运行Kruskal，而没有选择边，我只是问一下我的算法是否有效。
共有1个答案
它不起作用。
在步骤3之后，新添加的边可能成为仅包含具有非常低成本的边的循环的一部分，因此在步骤3和4之后，MST的总成本可以显著增加。
另一方面，该图可能包含与在步骤3中选择的边具有类似成本的另一个边，当将其添加到MST中时，该边将是另一个循环的一部分，例如，包含具有相对高成本的边。为步骤3选择这个边，然后应用步骤4将导致另一个生成树，比由提出的算法生成的树更好。
-
设T=(V，E)是一棵顶点和边的树，代价已知。我们想构造一个最小权完备图G=(V,E')，它的唯一最小生成树是T。 示例：考虑下面的树T，红色边具有给定的代价。将添加虚线边以从这棵树构造一个完整的图。 作为其唯一MST而跨越T的最小权完备图G如下所示： 2）对MST的所有其他边，权重，按权重递减的顺序重复。进行只包括而不包括其他MST边的切割。此切割的任何未知非MST边的权重应为。 问题： 1）上
-
假设我选择V(H)={a,e,f}和e(H)={ae,af,fe} 现在，对于每条边e∈e(H)，我们用e'记下了（来自原始图G的） 达到这个最小值的边。所以E'={bc,df,eg},因为bc=4,df=9,eg=8,是连接我的元件的最小边。我在H中有一个相对于代价函数C′的最小生成树，而a′是这棵树的边集。 但是我的A'的边和E'的没有一条是一样的。
-
考虑一个有n个顶点和m条边的无向图。假设边有两种类型:m1红色边和m2绿色边。因此m=m1+m2。红色边缘的权重为1，绿色边缘的权重为2。设计并分析了一种计算这种图的最小生成树的有效算法
-
我需要一些关于Prim的算法问题的帮助： 设T是图G的一个由Prim算法得到的最小生成树。设Gnew是在G上增加一个新的顶点和一些带权的边，将新的顶点连接到G上的一些顶点而得到的图，我们能把其中一条新的边加到T上构造Gnew的最小生成树吗？如果你回答是，请解释是怎样做的；如果没有，请解释原因。 提前谢谢！！
-
这里有一个图，我需要用Prim和Kruskal的算法找到G的最小生成树。 我用普里姆的算法找到了最小生成树。这是我的尝试。 我很难用Kruskal的算法找到最小生成树。我看过许多与Kruskal的图算法相关的视频，但最终得到的图与Prim的算法相同。 谁能给我演示一下如何用Kruskal的算法找到图的最小生成树吗？
-
无向图最小生成树的Prim算法 思路说明 假设点A,B,C,D,E,F，两点之间有连线的，以及它们的距离分别是：(A-B:7);(A-D:5);(B-C:8);(B-D:9);(B-E:7);(C-E:5);(D-E:15);(D-F:6);(E-F:8);(E-G:9);(F-G:11) 关于Prim算法的计算过程，参与维基百科的词条：普里姆算法 将上述点与点关系以及两点之间距离（边长，有的文献