最小的生长树：Kruskal＆Prim-Java 学习之路

我正在修改测试，并且在图表中遇到了两个与最小生成树相关的问题，我不确定并且想要测试我的答案 .

第一个问：如果图形有多个最小生成树，Kruskal和Prim的最小生成树算法会生成相同的树吗？我认为它们不一定是因为算法不同 . Kruskal依赖于按重量排序的边缘，而Prim则没有，因此它们可以从不同的顶点开始，从而生成不同的树 .

第二个问题是：如果图形具有多个最小生成树，那么Kruskal的算法应如何适应以生成所有这些？我认为需要允许通过顶点的循环结构，以便每次开始顶点都会改变，因为边缘值可能是相同的 . 因此，通过将每个顶点依次作为起始顶点来生成树 . 换句话说，也可以按顶点编号排序，而不是仅按边缘权重排序 .

1 回答

1
如果图形具有多个最小生成树，Kruskal和Prim的最小生成树算法是否会生成相同的树？

不，Prims和Kruskals算法不必生成相同的MST . 图形可以包含许多MST，并且两种算法都可以生成不同的MST . 但是两个MST的边缘类型必然是相同的 . 也就是说，如果你制作两个MST边缘的多重集合，那么两个多重集合肯定是相等的 . 你可以找到这个证据here

如果图形具有多个最小生成树，那么Kruskal的算法应该如何适应以生成所有这些？

似乎没有直接减少kruskal的MST算法来查找图中的所有MST . 你最好的选择是

第1步：在kruskals中对图形的边缘进行排序 .

第2步：现在对于排序列表中的每个边缘，可能会发生两件事 . 边缘是在MST中还是不在 . 因此，对于排序列表中的每个边，我们将讨论这两种情况并创建两个新的Union-Find数据结构并在其他边上递归 .

伪代码：
```
Step1: sort edges in ascending order
Step2: now call printAllMsts(0, new UnionFind(V))

void printAllMsts(int edgeNum, UnionFind U){
    if(edgeNum == edges.length){  // If no more edges to add
        if(U.numEdges == V-1){    // If U has V-1 edges, then we have an MST
             printMst();
        }
        return;
    }

    if(edges[edgeNum+1] == edges[edgeNum]){
         printAllMsts(edgeNum+1, U); // when E is not taken in the MST   
    }

    edge E = edges[edgeNum];
    If(E can be a part of some MST){
        UnionFind newU = new UnionFind(U);
        newU.add(E);
    }

    printAllMsts(edgeNum+1, newU);
}
```
算法的运行时间取决于图中边的数量和类型 . 问题的最坏情况输入是当图中的所有边长度相同时 . 运行时间至少是O（V * numberOfMsts），因为只要有可能存在不同的MST，就会克隆当前的Union-Find数据结构，这需要花费O（V）时间 .
回复于 2024-05-02T13:51:29+08:00

最小的生长树：Kruskal＆Prim

1 回答

相关问题