克鲁斯卡尔算法的思想（克鲁斯卡尔算法一定要画图吗）

本文目录

• 克鲁斯卡尔算法一定要画图吗
• 数据结构中图的克鲁斯卡尔算法的基本思想是
• 克鲁斯卡尔算法的时间复杂度为多少
• 数据结构 7.6 克鲁斯卡尔算法
• 克鲁斯卡尔算法求最小生成树
• 图的最小生成树算法(Prim和Kruskal)
• kruskal算法是什么
• 图所示是一个无向带权图,请分别按Prim算法和Kruskal算法求最小生成树.
• 克鲁斯卡尔算法可以回到起始点吗

克鲁斯卡尔算法一定要画图吗

1）克鲁斯卡尔算法概念
克鲁斯卡尔算法是求连通网的最小生成树的另一种方法。与普里姆算法不同，它的时间复杂度为O（eloge）（e为网中的边数），所以，适合于求边稀疏的网的最小生成树
（2）实现思路
对于任意一个连通网的最小生成树来说，在要求总的权值最小的情况下，最直接的想法就是将连通网中的所有边按照权值大小进行升序排序，从小到大依次选择。
克鲁斯卡尔算法的具体思路是：将所有边按照权值的大小进行升序排序，然后从小到大一一判断，条件为：如果这个边不会与之前选择的所有边组成回路，就可以作为最小生成树的一部分；反之，舍去。直到具有 n 个顶点的连通网筛选出来 n-1 条边为止。筛选出来的边和所有的顶点构成此连通网的最小生成树；

数据结构中图的克鲁斯卡尔算法的基本思想是

基本思想是：设有一个有n个顶点的连通网络N=｛V，E｝，最 初先构造一个只有n个顶点，没有边的非连通图 T=｛ V，￠｝，图中每个顶点自成一个 连通分量。当在E中选到一条具有最小权值的边时，若该边的两个顶点落在不同的连通 分量上，则将此边加人到T中；否则将此边舍去，重新选择一条权值最小的边。如此重复 下去，直到所有顶点在同一个连通分量上为止。

克鲁斯卡尔算法的时间复杂度为多少

时间复杂度为O(|E|log|E|)，其中E和V分别是图的边集和点集。

基本思想是先构造一个只含 n 个顶点、而边集为空的子图，把子图中各个顶点看成各棵树上的根结点，之后，从网的边集 E 中选取一条权值最小的边，若该条边的两个顶点分属不同的树，则将其加入子图，即把两棵树合成一棵树。

反之，若该条边的两个顶点已落在同一棵树上，则不可取，而应该取下一条权值最小的边再试之。依次类推，直到森林中只有一棵树，也即子图中含有 n-1 条边为止。

扩展资料：

克鲁斯卡尔算法证明

假设G=(V,E) 是一个具有n个顶点的连通网，T=(U,TE)是G的最小生成树，U的初值等于V，即包含有G中的全部顶点，TE的初值为空集。该算法的基本思想是：将图G中的边按权值从小到大的顺序依次选取。

若选取的边使生成树T不形成回路，则把它并入TE中，保留作为T的一条边，若选取的边使生成树T形成回路，则将其舍弃，如此进行下去直到TE中包含n-1条边为止，此时的T即为最小生成树。

克鲁斯卡尔算法，至多对e条边各扫描一次，每次选择最小代价的边仅需要O(loge)的时间。因此，克鲁斯卡尔算法的时间复杂度为O(eloge)。 

数据结构 7.6 克鲁斯卡尔算法

　　希赛教育计算机专业考研专业课辅导招生

　　希赛教育计算机专业考研专业课辅导视频

　　希赛教育计算机考研专业课在线测试系统

　　克鲁斯卡尔算法的基本思想为 为使生成树上总的权值之和达到最小 则应使每一条边上的权值尽可能地小 自然应从权值最小的边选起 直至选出n 条互不构成回路的权值最小边为止 具体作法如下 首先构造一个只含n个顶点的森林 然后依权值从小到大从连通网中选择不使森林中产生回路的边加入到森林中去 直至该森林变成一棵树为止 这棵树便是连通网的最小生成树

　　由于生成树上不允许有回路 因此并非每一条居当前权值最小的边都可选 例如 在依次选中了(e f) (b c) (e d) 和 (f g) 的四条边之后 权值最小边为 (g d) 由于 g 和 d 已经连通 若加上(g d) 这条边将使生成树上产生回路 显然这条边不可取 同理边 (f d) 也不可取 之后则依次取 (a g) 和 (a b) 两条边加入到生成树

克鲁斯卡尔算法求最小生成树

克鲁斯卡尔算法的基本思想，这是我自己结合教材理解的，难免有误，谨慎参考：
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：将上面我们记录的那些边连接起来就行了！这就是最小生成树，附本人手绘：

图的最小生成树算法(Prim和Kruskal)

***隐藏网址***
测试图如图所示：

思想：先选取一个顶点加入最小生成树，再选取与该顶点相连的边中的最小权值对应的顶点加入生成树，将这两个顶点作为一棵新的最小生成树，继续判断与该树相连的边的最小权值对应的顶点，并将其加入最小生成树，直到所有顶点均加入生成树为止。

测试程序

测试结果：

思想：将图的存储结构使用边集数组的形式表示，并将边集数组按权值从小到大排序，遍历边集数组，每次选取一条边并判断是否构成环路，不会构成环路则将其加入最小生成树，最终只会包含n-1条边(n为无向图的顶点数)。

边集数组的结构如图所示：

测试程序：

测试结果：

最小生成树为：

普里姆算法针对顶点展开，通过不断寻找与已构建的生成树的最小边来不断构建新的生成树。普里姆算法对于稠密图，也就是边数非常多的情况会更好一些，因为其是通过顶点来展开的。算法时间损耗主要来源于嵌套的for循环，所以时间复杂度为O(n^2)。

克鲁斯卡尔算法针对边展开，通过对边集数组的遍历来构建最小生成树，但是过程中必须避免构成环路。克鲁斯卡尔算法对于稀疏图，也就是边数较少的情况效率会很高。此算法的Find函数由边数e决定，时间复杂度为O(loge)，再加上外层for循环的e次，所以时间复杂度为O(eloge)。

kruskal算法是什么

kruskal算法是求加权连通图的最小生成树的算法。

kruskal算法总共选择n- 1条边，(共n个点)所使用的贪心准则是:从剩下的边中选择一条不会产生环路的具有最小耗费的边加入已选择的边的集合中。注意到所选取的边若产生环路则不可能形成一棵生成树。

kruskal算法分e步，其中e是网络中边的数目。按耗费递增的顺序来考虑这e 条边，每次考虑一条边。当考虑某条边时，若将其加入到已选边的集合中会出现环路，则将其抛弃，否则，将它选入。

Kruskal算法基本思想：

每次选不属于同一连通分量(保证不生成圈)且边权值最小的顶点，将边加入MST，并将所在的2个连通分量合并，直到只剩一个连通分量。

排序使用Quicksort(O(eloge))。

检查是否在同一连通分量用Union-Find，每次Find和union运算近似常数。

Union-Find使用rank启发式合并和路径压缩。

总复杂度O(eloge)=O(elogv) (因为e《n(n-1)/2)。

图所示是一个无向带权图,请分别按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的最小生成树。

克鲁斯卡尔（Kruskal）算法

基本思想

假设N=(V,E)是一个具有n个顶点的连通网，

（1）将n个顶点看成n个集合；

（2）按权值由小到大的顺序选择边，所选边应满足两个顶点不在同一个顶点集合内，将该边放到生成树边的集合中。同时将该边的两个顶点所在的顶点集合合并；

（3）重复（2），直到所有的顶点都在同一个顶点集合内。  

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

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

克鲁斯卡尔算法可以回到起始点吗

可以。克鲁斯卡尔(Kruskal)算法，是用来求加权连通图的最小生成树的算法。
基本思想：按照权值从小到大的顺序选择n-1条边，并保证这n-1条边不构成回路。
具体做法：首先构造一个只含n个顶点的森林，然后依权值从小到大从连通网中选择边加入到森林中，并使森林中不产生回路，直至森林变成一棵树为止。