《数据结构与算法》——图的最小生成树之克鲁斯卡尔算法（Kruskal）总结

编程入门行业动态更新时间:2024-10-19 08:46:14

《数据结构与<a href=https://www.elefans.com/category/jswz/34/1770096.html style= 算法》——图的最小生成树之克鲁斯卡尔算法（Kruskal）总结"/>

《数据结构与算法》——图的最小生成树之克鲁斯卡尔算法（Kruskal）总结

在考研中，图的应用所包含的一个重要部分被称为最小生成树，其中教材中给出了两个算法，Prime算法和kruskal算法。这是两个思想完全不同的算法，下面即为关于这两个算法中的kruskal算法的总结。

既然Prime算法已经总结完了，那就趁热打铁把克鲁斯卡尔算法也总结一下吧，总结完之后我有直觉，今年应该不考最小生成树，嗯，有这个直觉，但毕竟是直觉哈。

故事发生在半个月前，今天继续这个故事……

《数据结构与算法》——图的最小生成树之克鲁斯卡尔算法（Kruskal）总结

定义

伪代码实现

性能分析及应用

性能分析

应用

参考文献

定义

什么是kruskal算法？它的核心思想是什么？

在此，我要引入一个小故事，一个大家都熟悉的故事。

一袋米要扛几楼，一袋米要扛二楼，一袋米有好多泪，一袋米要我洗嘞，口口有泥，谁给你一袋米呦，辛辣天森……

（emmm，对不起，错片场了……）

（这个才对，百度搜图）

故事发生的背景在北宋末年宣和年间(公元1119-1125年)。当时宋皇室衰颓、腐败。宋微宗贪图享受，滥用坏人蔡京为宰相，穷奢极侈，对人民又横征暴敛，弄得民不聊生，逼得许多人铤而走险，盗贼四起。当时便有了这36天罡与72地煞共108好汉“替天行道，劫富济贫”的故事。话说一开始这108好汉中有些人或远或近都存在一些关系，但是能拿出来的关系很少，即不是每两个人之间都有关系，但又可以通过某些联系将所有人都连起来。譬如：一开始梁山上只有｛朱贵、杜迁、宋万｝三位好汉，而东溪村里有七星聚义中的6位好汉，二龙山上有鲁智深、武松和杨志，……，即他们从一个个独立的个体聚集成了一个一个的小集体，而集体之间又存在着联系，譬如：李逵一直崇拜宋江，鲁智深和林冲有很好的交情，武松与孙二娘和张青二人又有着很好的交情，等等，所以他们又通过一个个的关系将小集体连成了较大的集体，最后连成了整个梁山水泊。

好，故事讲完了，总起来讲就是其中各自首先和关系最近的人抱团然后，再找关系次近的人或集体抱团，最后报成了一个大团，它体现的思想和克鲁斯卡尔算法的思想是极其类似的，但也有些许不同，下面描述克鲁斯卡尔算法的思想。

即核心思想为：先构造一个只含 n 个顶点、而边集为空的子图，把子图中各个顶点看成各棵树上的根结点，之后，从网的边集 E 中选取一条权值最小的边，若该条边的两个顶点分属不同的树，则将其加入子图，即把两棵树合成一棵树，反之，若该条边的两个顶点已落在同一棵树上，则不可取，而应该取下一条权值最小的边再试之。依次类推，直到森林中只有一棵树，也即子图中含有 n-1 条边为止。（百度百科--克鲁斯卡尔算法）

伪代码实现

/*****************************
Description: 图的最小生成树之克鲁斯卡尔算法（Kruskal）
******************************/
//MiniTree_Kruskal
struct Edge{int v1,v2;//两个端点 int weight;//权值 bool flag;//访问标记 
}; 
struct VNode{int num;//编号Elemtype data;// 结点信息 
}; 
struct Graph{Edge edge[EMAX];VNode node[VMAX];int edgenum;int vexnum;
};int MiniEdge(Edge e[],int len){//用于获取合法的最小权值边//e为边集，len为集合中元素个数 int w=INF;//置为正无穷int num = 0; for(int i = 1;i<=len;i++)if(!e[i].flag && w>e[i].weight){w = e[i].weight;num = i;}return num;
}//MiniEdgeint getParent(int son,int parent[]){//用于获取某点的集合编号//son为结点值，parent为根集合while(son!=-1 && son!=parent[son])son = parent[son];return son;
}//getParentbool setParent( Edge e,int parent[]){//用于判断两点是否属于一个集合//若不属于一个集合则进行合并 //e为边结点，parent为根集合int v1p = getParent(e.v1,parent);int v2p = getParent(e.v2,parent); if(v1p!=v2p){if(v1p==-1)parent[e.v1]=e.v2;elseparent[e.v2]=e.v1;}else{if(v1p==-1){parent[e.v1]=e.v1;parent[e.v2]=e.v1;}else//二者属于同一个连通分量 return 0;}//else return 1;
}//getParentvoid MiniTree_Kruskal(Graph G){int parent[G.vexnum];for(int i = 1;i<=G.vexnum; i++)parent[i] = -1;//置散点标记 for(int i = 1;i<=G.edgenum; i++)G.edge[i].flag = 0;	//置未访问标记 int pe =  MiniEdge(G.edge,G.edgenum);//获取第一条最小权值边	while(pe){//遍历所有的边G.edge[pe].flag = 1;//置访问标记if(setParent(G.edge[pe],parent))//如果该边加入生成树集合中printf("边：%d\t%d",G.edge.v1,G.edge.v2);pe =  MiniEdge(G.edge,G.edgenum);//获取下一条最小权值边	}//while
}//MiniTree_Kruskal

性能分析及应用

性能分析

空间复杂度：

在算法中借用了一个并查集的结构应用，即parent数组，故空间复杂度为o(n)。

时间复杂度：

该算法实现时其最消耗时间的部分即为核心部分的while循环，每次循环会找出一条最短边，每次找最短边都需要对整个边集进行遍历，即e*e的时间复杂度，前面还有两个对parent和flag初始化的循环，但是一个连通图中e>=v-1,为一个数量级或e为高阶数量级，所以消耗的时间为线性的，不予考虑，故时间复杂度为o(e^2)，与边的多少有关，适用于边数少的图（稀疏图）。