克鲁斯卡尔算法的基本思想？克鲁斯卡尔算法求最小生成树

本文目录

• 克鲁斯卡尔算法的基本思想
• 克鲁斯卡尔算法求最小生成树
• 克鲁斯卡尔算法的时间复杂度为多少
• 克鲁斯卡尔算法
• 无论用普里姆算法或者是克鲁斯卡尔算法求最小生成树，得出的结果应该一样么
• 什么是克鲁斯卡尔算法
• 克鲁斯卡尔时间复杂度怎么算出来的
• 数据结构里提到的普里母和克鲁斯卡尔分别是哪个国家的
• 数据结构中图的克鲁斯卡尔算法的基本思想是
• c加加提问，克鲁斯卡尔算法是什么

克鲁斯卡尔算法的基本思想

先构造一个只含 n 个顶点、而边集为空的子图，把子图中各个顶点看成各棵树上的根结点，之后，从网的边集 E 中选取一条权值最小的边，若该条边的两个顶点分属不同的树，则将其加入子图，即把两棵树合成一棵树，反之，若该条边的两个顶点已落在同一棵树上，则不可取，而应该取下一条权值最小的边再试之。依次类推，直到森林中只有一棵树，也即子图中含有 n-1 条边为止。　　时间复杂度为为O(e^2), 使用并查集优化后复杂度为 O（eloge），与网中的边数有关，适用于求边稀疏的网的最小生成树。

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

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

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

时间复杂度为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)。 

参考资料来源：百度百科——克鲁斯卡尔算法

克鲁斯卡尔算法

你确定要用邻接表吗？因为在克鲁斯卡尔算法里只需要存储边及费用，用邻接表意义不大，还不好排序。以下给出并查集实现的克鲁斯卡尔算法，求解生成网络的最小费用，并输出生成网络里的路径。#include《iostream》#include《algorithm》using namespace std;int p,rank;int cho;struct edge{ int u,v,w;//u表示起始点编号，v表示终点编号，w表示该路径费用}e;int n,m;//n表示点的个数，m表示路径数void Init(){ int i; for(i=1;i《=n;i++) { p[i]=i; rank[i]=0; }}bool cmp(edge a,edge b){ return a.w《b.w;}int Find(int t){ if(p[t]!=t) { p[t]=Find(p[t]); } return p[t];}int Union(int a,int b){ int x,y; x=Find(a); y=Find(b); if(rank[x]》rank[y]) { p[y]=x; } else { p[x]=y; if(rank[x]==rank[y]) rank[y]++; } return 0;}int main(){ scanf(“%d%d“,&n,&m); int i,j; for(i=0;i《m;i++) { scanf(“%d%d%d“,&e[i].u,&e[i].v,&e[i].w); } Init(); sort(e,e+m,cmp); int cnt=0,ans=0; for(i=0;i《m;i++) { if(Find(e[i].u)!=Find(e[i].v)) { cnt++; ans+=e[i].w; Union(e[i].u,e[i].v); cho[++cho]=i; if(cnt==n-1) break; } } printf(“%d\n“,ans); for(j=1;j《=cho;j++) { printf(“%d %d\n“,e[cho[j]].u,e[cho[j]].v); } return 0;}

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

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

什么是克鲁斯卡尔算法

设有一个有n个顶点的连通网N={V,E},最初先构造一个只有n个顶点，没有边的非连通图T={V, E},图中每个顶点自成一个连通分量。当在E中选到一条具有最小权值的边时,若该边的两个顶点落在不同的连通分量上，则将此边加入到T中；否则将此边舍去，重新选择一条权值最小的边。如此重复下去，直到所有顶点在同一个连通分量上为止。2算法描述编辑克鲁斯卡尔算法的时间复杂度为O（eloge）(e为网中边的数目)，因此它相对于普里姆算法而言，适合于求边稀疏的网的最小生成树。克鲁斯卡尔算法从另一途径求网的最小生成树。假设连通网N=（V，{E}），则令最小生成树的初始状态为只有n个顶点而无边的非连通图T=（V，{∮}），图中每个顶点自成一个连通分量。在E中选择代价最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入到T中，否则舍去此边而选择下一条代价最小的边。依次类推，直至T中所有顶点都在同一连通分量上为止。例如图为依照克鲁斯卡尔算法构造一棵最小生成树的过程。代价分别为1，2，3，4的四条边由于满足上述条件，则先后被加入到T中，代价为5的两条边（1，4）和（3，4）被舍去。因为它们依附的两顶点在同一连通分量上，它们若加入T中，则会使T中产生回路，而下一条代价（=5）最小的边（2，3）联结两个连通分量，则可加入T。因此，构造成一棵最小生成树。上述算法至多对 e条边各扫描一次，假若以“堆”来存放网中的边，则每次选择最小代价的边仅需O（loge）的时间（第一次需O（e））。又生成树T的每个连通分量可看成是一个等价类，则构造T加入新的过程类似于求等价类的过程，由此可以以“树与等价类”中介绍的 mfsettp类型来描述T，使构造T的过程仅需用O（eloge）的时间，由此，克鲁斯卡尔算法的时间复杂度为O（eloge）。 

克鲁斯卡尔时间复杂度怎么算出来的

Kruskal算法的时间复杂度由排序算法决定，若采用快排则时间复杂度为O(N log N)。kruskal算法：求加权连通图的最小生成树的算法。kruskal算法总共选择n- 1条边，（共n个点）所使用的贪婪准则是：从剩下的边中选择一条不会产生环路的具有最小耗费的边加入已选择的边的集合中。注意到所选取的边若产生环路则不可能形成一棵生成树。kruskal算法分e 步，其中e 是网络中边的数目。按耗费递增的顺序来考虑这e 条边，每次考虑一条边。当考虑某条边时，若将其加入到已选边的集合中会出现环路，则将其抛弃，否则，将它选入。假设WN=(V,{E})是一个含有 n 个顶点的连通网，则按照克鲁斯卡尔算法构造最小生成树的过程为：先构造一个只含 n 个顶点，而边集为空的子图，若将该子图中各个顶点看成是各棵树上的根结点，则它是一个含有 n 棵树的一个森林。之后，从网的边集 E 中选取一条权值最小的边，若该条边的两个顶点分属不同的树，则将其加入子图，也就是说，将这两个顶点分别所在的两棵树合成一棵树；反之，若该条边的两个顶点已落在同一棵树上，则不可取，而应该取下一条权值最小的边再试之。依次类推，直至森林中只有一棵树，也即子图中含有 n-1条边为止。

数据结构里提到的普里母和克鲁斯卡尔分别是哪个国家的

普里母算法和克鲁斯卡尔方法求最小生成树完整程序

1、普里姆算法（Prim算法），图论中的一种算法，可在加权连通图里搜索最小生成树。意即由此算法搜索到的边子集所构成的树中，不但包括了连通图里的所有顶点（英语：Vertex (graph theory)），且其所有边的权值之和亦为最小。该算法于1930年由捷克数学家沃伊捷赫·亚尔尼克（英语：Vojtěch Jarník）发现；并在1957年由美国计算机科学家罗伯特·普里姆（英语：Robert C. Prim）独立发现；1959年，艾兹格·迪科斯彻再次发现了该算法。因此，在某些场合，普里姆算法又被称为DJP算法、亚尔尼克算法或普里姆－亚尔尼克算法

2、Kruskal算法是一种用来寻找最小生成树的算法，由Joseph Kruskal在1956年发表。用来解决同样问题的还有Prim算法和Boruvka算法等。三种算法都是贪婪算法的应用。和Boruvka算法不同的地方是，Kruskal算法在图中存在相同权值的边时也有效。

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

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

c加加提问，克鲁斯卡尔算法是什么

克鲁斯卡尔算法，从边的角度求网的最小生成树，时间复杂度为O(eloge)。和普里姆算法恰恰相反，更适合于求边稀疏的网的最小生成树。对于任意一个连通网的最小生成树来说，在要求总的权值最小的情况下，最直接的想法就是将连通网中的所有边按照权值大小进行升序排序，从小到大依次选择。由于最小生成树本身是一棵生成树，所以需要时刻满足以下两点：

• 生成树中任意顶点之间有且仅有一条通路，也就是说，生成树中不能存在回路；

• 对于具有 n 个顶点的连通网，其生成树中只能有 n-1 条边，这 n-1 条边连通着 n 个顶点。

连接 n 个顶点在不产生回路的情况下，只需要 n-1 条边。

• 所以克鲁斯卡尔算法的具体思路是：将所有边按照权值的大小进行升序排序，然后从小到大一一判断，条件为：如果这个边不会与之前选择的所有边组成回路，就可以作为最小生成树的一部分；反之，舍去。直到具有 n 个顶点的连通网筛选出来 n-1 条边为止。筛选出来的边和所有的顶点构成此连通网的最小生成树。

判断是否会产生回路的方法为：在初始状态下给每个顶点赋予不同的标记，对于遍历过程的每条边，其都有两个顶点，判断这两个顶点的标记是否一致，如果一致，说明它们本身就处在一棵树中，如果继续连接就会产生回路；如果不一致，说明它们之间还没有任何关系，可以连接。

• 假设遍历到一条由顶点 A 和 B 构成的边，而顶点 A 和顶点 B 标记不同，此时不仅需要将顶点 A 的标记更新为顶点 B 的标记，还需要更改所有和顶点 A 标记相同的顶点的标记，全部改为顶点 B 的标记。

图 1 连通网

请点击输入图片描述

• 例如，使用克鲁斯卡尔算法找图 1 的最小生成树的过程为：
• 首先，在初始状态下，对各顶点赋予不同的标记（用颜色区别），如下图所示：

（1）

请点击输入图片描述

• 对所有边按照权值的大小进行排序，按照从小到大的顺序进行判断，首先是（1，3），由于顶点 1 和顶点 3 标记不同，所以可以构成生成树的一部分，遍历所有顶点，将与顶点 3 标记相同的全部更改为顶点 1 的标记，如（2）所示：

（2）

请点击输入图片描述

• 其次是（4，6）边，两顶点标记不同，所以可以构成生成树的一部分，更新所有顶点的标记为：

（3）

请点击输入图片描述

• 其次是（2，5）边，两顶点标记不同，可以构成生成树的一部分，更新所有顶点的标记为：

（4）

请点击输入图片描述

• 然后最小的是（3，6）边，两者标记不同，可以连接，遍历所有顶点，将与顶点 6 标记相同的所有顶点的标记更改为顶点 1 的标记：

（5）

请点击输入图片描述

• 继续选择权值最小的边，此时会发现，权值为 5 的边有 3 个，其中（1，4）和（3，4）各自两顶点的标记一样，如果连接会产生回路，所以舍去，而（2，3）标记不一样，可以选择，将所有与顶点 2 标记相同的顶点的标记全部改为同顶点 3 相同的标记：

（6）

请点击输入图片描述

• 当选取的边的数量相比与顶点的数量小 1 时，说明最小生成树已经生成。所以最终采用克鲁斯卡尔算法得到的最小生成树为（6）所示。
• 实现代码：#include “stdio.h“#include “stdlib.h“#define MAX_VERtEX_NUM 20#define VertexType inttypedef struct edge{VertexType initial;VertexType end;VertexType weight;}edge[MAX_VERtEX_NUM];//定义辅助数组typedef struct {VertexType value;//顶点数据int sign;//每个顶点所属的集合}assist[MAX_VERtEX_NUM];assist assists;//qsort排序函数中使用，使edges结构体中的边按照权值大小升序排序int cmp(const void *a,const void*b){return  ((struct edge*)a)-》weight-((struct edge*)b)-》weight;}//初始化连通网void CreateUDN(edge *edges,int *vexnum,int *arcnum){printf(“输入连通网的边数：\n“);scanf(“%d %d“,&(*vexnum),&(*arcnum));printf(“输入连通网的顶点：\n“);for (int i=0; i《(*vexnum); i++) {scanf(“%d“,&(assists[i].value));assists[i].sign=i;}printf(“输入各边的起始点和终点及权重：\n“);for (int i=0 ; i《(*arcnum); i++) {scanf(“%d,%d,%d“,&(*edges)[i].initial,&(*edges)[i].end,&(*edges)[i].weight);}}//在assists数组中找到顶点point对应的位置下标int Locatevex(int vexnum,int point){for (int i=0; i《vexnum; i++) {if (assists[i].value==point) {return i;}}return -1;}int main(){int arcnum,vexnum;edge edges;CreateUDN(&edges,&vexnum,&arcnum);//对连通网中的所有边进行升序排序，结果仍保存在edges数组中qsort(edges, arcnum, sizeof(edges), cmp);//创建一个空的结构体数组，用于存放最小生成树edge minTree;//设置一个用于记录最小生成树中边的数量的常量int num=0;//遍历所有的边for (int i=0; i《arcnum; i++) {//找到边的起始顶点和结束顶点在数组assists中的位置int initial=Locatevex(vexnum, edges[i].initial);int end=Locatevex(vexnum, edges[i].end);//如果顶点位置存在且顶点的标记不同，说明不在一个集合中，不会产生回路if (initial!=-1&& end!=-1&&assists[initial].sign!=assists[end].sign) {//记录该边，作为最小生成树的组成部分minTree[num]=edges[i];//计数+1num++;//将新加入生成树的顶点标记全不更改为一样的for (int k=0; k《vexnum; k++) {if (assists[k].sign==assists[end].sign) {assists[k].sign=assists[initial].sign;}}//如果选择的边的数量和顶点数相差1，证明最小生成树已经形成，退出循环if (num==vexnum-1) {break;}}}//输出语句for (int i=0; i《vexnum-1; i++) {printf(“%d,%d\n“,minTree[i].initial,minTree[i].end);}return 0;}
• 测试数据：

输入连通网的边数：6 10输入连通网的顶点：123456输入各边的起始点和终点及权重：1,2,61,3,11,4,52,3,52,5,33,4,53,5,63,6,44,6,25,6,61,34,62,53,62,3