primkruskal算法

① Kruskal算法和Prim算法构造它的一棵最小代价生成树的过程

Prim算法复杂度：O(n2), 与边无关，适合求边稠密的网的最小生成树。

算法思想：假设N={V,{E}}是连通网，TE是N上最小生成树中边的集合。算法从U={u0},TE ={}开始，重复执行下述操作：在所有u∈U,v∈V-U的边（u，v）∈E中找一条代价最小的边（u0,v0）并入集合TE，同时v0并入U，直至U=V为止。

Kruskal算法复杂度：O(eloge)，相对于Prim而言，适合求边稀疏的网的最小生成树。

算法思想：最小生成树的初始状态为只有n个顶点而无边的非连通图T=(V,{})，图中每个顶点自成一个连通分量。在E中选择代价最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入到T中，否则舍去次边而选择下一条代价最小的边。直至T中所有顶点都在同一连通分量上为止。

② prim和kruscal算法得到的最小生成树是否一样

应该不一样。可以用一个图根据两算法试一下，若一样，再修改图，之后应该就可以了。
（网络或者查书本更加有效……）
构造G的最小生成树的Prim算法的基本思想是：首先置S={1}，然后，只要S是V的真子集，就作如下的贪心选择：选取满足条件iS，jV-S，且c[i][j]最小的边，将顶点j添加到S中。
这个过程一直进行到S=V时为止。
Kruskal算法构造G的最小生成树：将所有的边按权从小到大排序。然后从第一条边开始，依边权递增的顺序查看每一条边，并按下述方法连接2个不同的连通分支：当查看到第k条边(v, w)时，如果端点v和w分别是当前2个不同的连通分支T1和T2中的顶点时，就用边(v, w)将T1和T2连接成一个连通分支，然后继续查看第k+1条边；如果端点v和w在当前的同一个连通分支中，就直接再查看第k+1条边。这个过程一直进行到只剩下一个连通分支时为止

③ prim算法和kruskal算法的区别

边数较少可以用Kruskal,因为Kruskal算法每次查找最短的边。 边数较多可以用Prim，因为它是每次加一个顶点，对边数多的适用。

④ 已知一个无向图如下图所示,要求分别用Prim和Kruskal算法生成最小树(假设以①为起点,试画出

p，树向外扩张，找最短外扩路径

k，增加一条不会造成回路的边(现在选中的边可以暂不相连)

按照prim是：（从起点到终点的边）

46，45，51，63，12，32

按照kruskal是：

46，15，45，63，12，32

克鲁斯卡尔算法思想先将边中的权值从小到大排序，每次找出候选边中权值最小的边，就将该边并入生成树中。重复此过程直到所有边都被检测完为止。

其中要注意的是克鲁斯卡尔算法需要用到并查集，以此来判断接下来要并入的边是否会和已并入的边构成回路。这两个图分别用普里姆和克鲁斯卡尔生成的最小生成树见图。

(4)primkruskal算法扩展阅读：

无向图G=<V,E>,其中：

1、V是非空集合，称为顶点集。

2、E是V中元素构成的无序二元组的集合，称为边集。

解释

直观来说，若一个图中每条边都是无方向的，则称为无向图。

无向边的表示

无向图中的边均是顶点的无序对，无序对通常用圆括号表示。

⑤ prim算法构造出的最小生成树唯一吗prim算法和kruskal算法构造出的最小生成树一样吗

不唯一，两种算法构造出的最小生成不一定相同。

⑥ 13.用Prim算法和Kruskal算法构造图的最小生成树,所得到的最小生成树是否相同

如果原来的图里面任何两条边长都不相同,那么最小生成树是唯一的,此时不管用什么方法算出来的都是一样的
但是如果图里有相等的边,那么最小生成树可能会不唯一,这样就无法保证不同的方法得到同一棵树（即使是同一个算法,只要图的编号方式改变也可能得到不同的最小生成树）

⑦ 图所示是一个无向带权图,请分别按Prim算法和Kruskal算法求最小生成树.

•普里姆（Prim）算法

基本思想

假设N=(V,E)是一个具有n个顶点的连通网，T=(U,TE)是所求的最小生成树，其中U是T的顶点集，TE是T的边集。

（1）初始U={u0}(u0∈V),TE=φ；

（2）在所有u∈U,v∈V-U的边中选一条代价最小的边（u0，v0）并入集合TE，同时将v0并入U；

（3）重复（2），直到U=V为止。

此时，TE中必含有n-1条边，则T=（V，{TE}）为N的最小生成树。

注意：1.最小生成树不唯一。

2.该图从节点最小开始。

⑧ 如何用浅显的语言解释Kruskal算法和Prim算法

不严谨的说：将全集分为遍历集合未遍历集。两种算法都是遍历集慢慢扩大为全集的过程。
Kruskal：集合中元素是边，每次从未遍历集中找一个最短边，如果遍历集包含它后不会构成回路，就包含，重复过程直到所有点都连通。
Prim：集合中元素是点，每次从未遍历集中找一个距离遍历集距离最近的点，将其包含，重复过程直到包含所有点。
当然对于Kruskal，遍历集并没有扩展为全集，把全部边都包含了也没有意义了。

⑨ 用普里姆（Prim）或克鲁斯卡尔（Kruskal）算法，画出下列无向网的最小生成树

如图，这是Prim算法构造最小生成树的每一步，这里是以A点为初始点。

最小生成树用权重是60

⑩ 如图1所示，用prim算法和Kruskal算法构造最小生成树。

prim算法：假设初始节点为A，则扩展的点的顺序为：
加入边AC，扩展C节点
加入边AB，扩展B节点
加入边CD，扩展D节点
加入边BF，扩展F节点
加入边DE，扩展E节点

所以最小生成树含有的边为：AC、AB、CD、BF、DE

kruskal算法：
加入边AC
加入边DE
加入边AB
加入边BF
加入边CD

最小生成树与上面一样