algorithm - 最小生成树与另一个不同

Question

假设我们有

无向图 g其中每个节点 i,1 <= i < n 都连接到所有 j,i < j <=n

和来源s .

我们想要找到与s 的最小距离树不同的最便宜 最小生成树的总成本(定义为所有边权重的总和) (即从通过在 s 上运行 prim/dijkstra 获得的 MST)至少有一条边。

解决这个问题的最佳方法是什么？因为目前，我只能想到某种定点迭代

1. 在 (g,s) 上运行 dijkstra获取引用图r我们需要区别于
2. costs := sum(edge_weights_of(r))
3. change := 0
4. 对于每个顶点u在 r ，运行 bfs 并注意每个到达的顶点 v从 u 开始的路径上的最长边至 v .
5. 遍历所有边e = (a,b)在 g : 并找到 e'=(a',b')那不在 r 中并最小化 newchange := weight(e') - weight(longest_edge(a',b'))
6. if(first_time_here OR newchange < 0 ) then change += newchange
7. if(newchange < 0) goto 4
8. result := costs + change

这似乎浪费了很多时间......它依赖于这样一个事实，即向生成树添加一条边会创建一个循环，我们可以从中删除最长的边。

我还考虑过使用 Kruskal 来获得整体最小生成树，并且仅在来自 prim 和 kruskal 的树恰好相同时才使用上述算法替换单个边，但这似乎并不工作，因为结果将高度依赖于运行 kruskal 期间选择的边缘。

有什么建议/提示吗？

Answer 1

你可以使用 Prim 的算法来做到这一点

Prim's algorithm:
let T be a single vertex x
while (T has fewer than n vertices)
{
    1.find the smallest edge connecting T to G-T
    2.add it to T
}

现在让我们修改它。

让你有一个最小生成树。说树(E,V)
使用这个算法

Prim's algorithm (Modified):
let T be a single vertex 
let isOther = false
while (T has fewer than n vertices)
{
    1.find the smallest edge (say e) connecting T to G-T
    2.If more than one edge is found, {
        check which one you have in E(Tree)
        choose one different from this 
        add it to T
        set isOther = true
      }
      else if one vertex is found {
        add it to T
        If E(Tree) doesn`t contain this edge, set isOther = true
        Else don`t touch isOther ( keep value ).
      }
}
If isOther = true, it means you have found another tree different from Tree(E,V) and it is T, 
Else graph have single minimum spanning tree