无论用普里姆算法或者是克鲁斯卡尔算法求最小生成树，得出的结果应该一样么

不总是一样的，克鲁斯卡尔算法是精确算法，即每次都能求得最优解，但对于规模较大的最小生成树问题，求解速度较慢。而普里姆算法是近似求解算法，虽然对于大多数最小生成树问题都能求得最优解，但相当一部分求得的是近似最优解。这是我个人见解。

克鲁斯卡尔算法的基本思想，这是我自己结合教材理解的，难免有误，谨慎参考：

1：将图中的n顶点看成是n个集合。解释为，图中共有6个顶点，那么就有六个集合。即a,b,c,d,e,f各自分别都是一个集合。｛a｝,｛b｝等。

2：按权值由小到大的顺序选择边。所选边应满足两个顶点不在同一个顶点集合内。将该边放到生成树边的集合，同时将该边的两个顶点所在的集合合并。这是书上的描述，可能有点难理解，这里解释一下：

首先，选择权值最小的边，即为图中的（a,c）边，此时a,c满足不在同一个顶点集合内，将这个边记录下来，然后合并这两个顶点的集合，即此时剩下五个顶点集合了，｛a,c｝,｛b｝,｛d｝,｛e｝，｛f｝

3：重复步骤2，直到所有的顶点都在同一个集合内！解释如下：

此时剩下的边中权值最小的为（d，f），满足不在同一个顶点集合，所以记录下该边，然后合并这两个顶点集合。新的顶点集合为｛a，c｝ ｛b｝ ｛e｝ ｛d，f｝

接着，继续重复，选择边（b，e），满足不在同一个顶点集合内，所以记录下该边，然后再次合并这两个集合，新的集合为｛a,c｝ ｛d,f｝ ｛b,e｝

继续，选择边（c,f）,满足不在同一个顶点集合内，所以记录下该边，然后合并这两个顶点所在的集合，新集合为｛a,c,d,f｝ ｛b,e｝

再继续，选择权值为15的边，发现边（c,d）和边（a,d）都不满足条件不在同一个顶点集合内，所以只能选择边（b,c），记录下该边，然后合并顶点集合，新集合为｛a,b,c,d,e,f｝，此时所有点都在同一集合内，所以结束！

4：将上面我们记录的那些边连接起来就行了！这就是最小生成树，附本人手绘：

看这段代码真令我头疼，我就告诉你思路吧！

并查集你会不会？如果会的话那就好办。

kruskal算法用到了一种贪心策略，首先要把边集数组以边的权值从小到大排序，然后一条边一条边的查找，如果边的两个端点不在一个集合内，则将此边添加到正在生长的树林中，并合并两个端点所在的集合，直到最小生成树已生成完毕。

核心伪代码如下（本人不习惯给完整的可编译的代码）：

func root(x:longint):longint;//查找i节点所在集合

var i,j,k:longint;

{i:=x;j:=x;

while i!=f[i] do i=f[i];

while j!=i do

{k=j;j=f[j];f[k]=i;}//路径压缩，若不压缩效率将很低

};//root

proc union(i,j,c:longint);

var x,y:longint;

{x=root(i);

y=root(j);

if x!=y then {inc(ans,c);inc(temp);f[y]=x;}

//若i和j分属两棵子树，则将此边添加到森林中，并合并其所在集合

};//union;

将边集数组按照边的权值从小到大排序;

for (i=1,i++,i=n) f[i]=i;//并查集初始化

for (i=1,i++,i=m)

{union(edge[i]x,edge[i]y,edge[i]z);

if temp==n-1 then break;

//若temp==n-1则最小生成树已生成完毕，退出

}//kruskal

if temp==n-1 then writeln(ans)//输出最小生成树的权值和

else writeln('No solution!');//若temp!=n-1，则说明此图为非连通图

kruskal算法的时间复杂度主要由排序方法决定，其排序算法只与带权边的个数有关，与图中顶点的个数无关，当使用时间复杂度为O（eloge）的排序算法时，克鲁斯卡算法的时间复杂度即为O（eloge），因此当带权图的顶点个数较多而边的条数较少时，使用克鲁斯卡尔算法构造最小生成树效果最好！

克鲁斯卡尔算法

假设 WN=(V,{E}) 是一个含有 n 个顶点的连通网，则按照克鲁斯卡尔算法构造最小生成树的过程为：先构造一个只含 n 个顶点，而边集为空的子图，若将该子图中各个顶点看成是各棵树上的根结点，则它是一个含有 n 棵树的一个森林。之后，从网的边集 E 中选取一条权值最小的边，若该条边的两个顶点分属不同的树，则将其加入子图，也就是说，将这两个顶点分别所在的两棵树合成一棵树；反之，若该条边的两个顶点已落在同一棵树上，则不可取，而应该取下一条权值最小的边再试之。依次类推，直至森林中只有一棵树，也即子图中含有 n-1条边为止。

普里姆算法

假设 WN=(V,{E}) 是一个含有 n 个顶点的连通网，TV 是 WN 上最小生成树中顶点的集合，TE 是最小生成树中边的集合。显然，在算法执行结束时，TV=V，而 TE 是 E 的一个子集。在算法开始执行时，TE 为空集，TV 中只有一个顶点，因此，按普里姆算法构造最小生成树的过程为：在所有“其一个顶点已经落在生成树上，而另一个顶点尚未落在生成树上”的边中取一条权值为最小的边，逐条加在生成树上，直至生成树中含有 n-1条边为止。

--以上传自>

主要有两个：

1普里姆（Prim)算法

特点：时间复杂度为O(n2)适合于求边稠密的最小生成树。

2克鲁斯卡尔（Kruskal)算法

特点：时间复杂度为O(eloge)(e为网中边数），适合于求稀疏的网的最小生成树。

证明：令G为任何一个与Kruskal算法产生的树F不同的树考虑构造F的过程令e为第一次选的一条不属于G的边如果我们将e加入G,我们会得到一个圈C这个圈不完全包含在F里面,因此在C中有一条不属于F的边f如果我们将e加入G并删除f,我们就得到了一个新的树H

我们想要证明H不比G贵这意味着e不比f贵用反证法假设f比e便宜

现在考虑这样一个问题：为什么Kruskal算法选择了f而不是e呢唯一的原因只可能是f被排除了,即f与加入e之前被选入F的边会形成一个圈但是所有这些已经被选的边都是G的边,因为e为第一次选的一条不属于G的边又f本身属于G,所以G就包含了一个圈,这是不可能的（G是树）这个矛盾证明了H不比G贵

因此我们可以用H来代替G,而且H比G更接近F（即H与F有更多相同的边）如果H不是F,重复以上步骤,我们得到一系列与H越来越接近的不比G贵的树这个过程迟早会以F终结,这就证明了F不比G贵

Kruskal算法的正确性也就得证

以上就是关于无论用普里姆算法或者是克鲁斯卡尔算法求最小生成树，得出的结果应该一样么全部的内容，包括:无论用普里姆算法或者是克鲁斯卡尔算法求最小生成树，得出的结果应该一样么、请用克鲁斯卡尔算法为下图构造最小生成树，谢谢。、克鲁斯卡尔算法 判断回路中的问题等相关内容解答，如果想了解更多相关内容，可以关注我们，你们的支持是我们更新的动力！