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

Kruskal算法的思想、证明及步骤Kruskal算法思想：把n个顶点看成看成n棵分离的树（每棵树只有⼀个顶点），每次选取可连接两个分离树中权值最⼩的边把两个分离的树合成⼀个新的树取代原来的两个分离树，如果重复n-1步后便得到最⼩⽣成树。

Kruskal算法步骤：T0存放⽣成树的边，初值为空C(T0) 最⼩⽣成树的权，初值为0VS 分离树顶点的集合，初值为 { {v1} {v2} … {v n} }A B W分别为边的顶点和权值数组，由⽤户输⼊1) T0←0, C(T0)←0, VS←{ {v1} {v2} … {v n} }, A, B, W按W排序后构成队列Q2) If n(VS)==1 then stop else goto 33) 取Q第⼀组数组(u, v, w) 并从Q中将其删除.4) If u, v 属于同⼀个集合 then goto 3 else 分属两个集合X, Y, goto 5.5) T0←T0∪(u, v), C(T0)←C(T0)+w, VS←VS-X-Y+X∪Y goto 2.Kruskal算法证明：树定义：⽆圈连通图。

引理1：⼀个图是树等价于⼀个图⽆圈且任意不相关联的顶点u, v ，图G+(u, v)则必存在唯⼀⼀个圈。

设由Kruskal算法⽣成的T0序列为e1, e2, e3 … e v-1，假设其不是最⼩⽣成树。

任意最⼩⽣成树T定义函数f(T)：T0中不存在于T中边在T0的下标。

设T1是使f(T)最⼤的变量，设f(T1)=k，即e k不存在于T1中，T1为树且e k不在T1中，所以由引理1得T1+e k必存在圈C，C上必有e,k ≠e k，e,k不在T0中。

现令T2 = T1 - e,k + e k，则T2也为⽣成树但由Kruskal算法可知e k是使e1, e2 … e k-1, e k⽆圈的权值最⼩的边，e1, e2 … e k-1, e ,k是树的⼦图必⽆圈故e,k的权值必定⼩于e k，即T2的总权值不⼤于T1的权值，因T1是最⼩⽣成树，故必T2也是最⼩⽣成树，但f(T2)＞k与k是f函数最⼤取值⽭盾，故T0是最⼩⽣成树。

Kruskal算法是一种用于求解最小生成树的算法，它的主要特点是按边的权值大小进行排序，并逐步添加边，直到构成一棵生成树为止。

在实际应用中，Kruskal算法通常被用来解决各种最小生成树的问题，比如公路修建、通信网络的建设、电路板的设计等等。

本文将着重介绍Kruskal算法的原理、步骤和具体应用，以期为读者提供全面的了解和指导。

一、Kruskal算法的原理Kruskal算法是一种基于贪心策略的算法，它通过不断地选择边来构建生成树，直到所有的顶点都被包含在生成树中。

其基本原理可以概括如下：1. 将图中的所有边按权值大小进行排序。

2. 依次从小到大选择边，并检查是否形成环路。

3. 如果没有形成环路，则将该边添加到生成树中。

Kruskal算法的核心思想是“先小后大”，即先选择权值较小的边，直到所有的顶点都被包含在生成树中。

由于Kruskal算法是基于边来构建生成树的，因此它适用于稀疏图和稠密图，而且在实际应用中通常具有较好的效率。

二、Kruskal算法的步骤Kruskal算法的具体步骤可以简单总结为以下几个步骤：1. 初始化：将图中的所有边按权值大小进行排序。

2. 创建一个空的数组T来存储最小生成树的边。

3. 依次从排序后的边集合中选择边e，并检查是否添加e会形成环路。

4. 如果不形成环路，则将边e添加到数组T中。

5. 直到T中包含了n-1条边为止，其中n为顶点的个数。

三、Kruskal算法的具体实现下面我们通过一个简单的示例来说明Kruskal算法的具体实现步骤。

示例：假设有如下的图G和边集合E：顶点集合V：{A, B, C, D, E, F, G, H}边集合E：{(A, B, 4), (A, H, 8), (B, C, 8), (B, H, 11), (C, D, 7), (C, F, 4), (C, I, 2), (D, E, 9), (D, F, 14), (E, F, 10), (F, G, 2), (G, H, 1), (G, I, 6), (H, I, 7)}我们可以按照如下的步骤来求解最小生成树：1. 首先对边集合E进行按权值的排序：(E, F, 2), (G, H, 1), (C, I, 2), (A, B, 4), (C, F, 4), (H, I, 7), (C, D, 7), (D, E, 9), (A, H, 8), (B, C, 8), (G, I, 6), (B, H, 11), (D, F, 14)2. 初始化一个空的数组T来存储最小生成树的边，初始化一个数组parent来记录每个顶点的父节点。

最⼩⽣成树---普⾥姆算法（Prim算法）和克鲁斯卡尔算法（Kruskal算法）最⼩⽣成树的性质：MST性质（假设N=(V,{E})是⼀个连通⽹，U是顶点集V的⼀个⾮空⼦集，如果（u，v）是⼀条具有最⼩权值的边，其中u属于U，v属于V-U，则必定存在⼀颗包含边（u，v）的最⼩⽣成树）普⾥姆算法（Prim算法)思路：以点为⽬标构建最⼩⽣成树1.将初始点顶点u加⼊U中，初始化集合V-U中各顶点到初始顶点u的权值；2.根据最⼩⽣成树的定义：从n个顶点中，找出 n - 1条连线，使得各边权值最⼩。

循环n-1次如下操作：（1）从数组lowcost[k]中找到vk到集合U的最⼩权值边，并从数组arjvex[k] = j中找到该边在集合U中的顶点下标(2)打印此边，并将vk加⼊U中。

（3）通过查找邻接矩阵Vk⾏的各个权值，即vk点到V-U中各顶点的权值，与lowcost的对应值进⾏⽐较，若更⼩则更新lowcost，并将k存⼊arjvex数组中以下图为例#include<bits/stdc++.h>using namespace std;#define MAXVEX 100#define INF 65535typedef char VertexType;typedef int EdgeType;typedef struct {VertexType vexs[MAXVEX];EdgeType arc[MAXVEX][MAXVEX];int numVertexes, numEdges;}MGraph;void CreateMGraph(MGraph *G) {int m, n, w; //vm-vn的权重wscanf("%d %d", &G->numVertexes, &G->numEdges);for(int i = 0; i < G->numVertexes; i++) {getchar();scanf("%c", &G->vexs[i]);}for(int i = 0; i < G->numVertexes; i++) {for(int j = 0; j < G->numVertexes; j++) {if(i == j) G->arc[i][j] = 0;else G->arc[i][j] = INF;}}for(int k = 0; k < G->numEdges; k++) {scanf("%d %d %d", &m, &n, &w);G->arc[m][n] = w;G->arc[n][m] = G->arc[m][n];}}void MiniSpanTree_Prim(MGraph G) {int min, j, k;int arjvex[MAXVEX]; //最⼩边在 U集合中的那个顶点的下标int lowcost[MAXVEX]; // 最⼩边上的权值//初始化,从点 V0开始找最⼩⽣成树Tarjvex[0] = 0; //arjvex[i] = j表⽰ V-U中集合中的 Vi点的最⼩边在U集合中的点为 Vjlowcost[0] = 0; //lowcost[i] = 0表⽰将点Vi纳⼊集合 U ，lowcost[i] = w表⽰ V-U中 Vi点到 U的最⼩权值for(int i = 1; i < G.numVertexes; i++) {lowcost[i] = G.arc[0][i];arjvex[i] = 0;}//根据最⼩⽣成树的定义：从n个顶点中，找出 n - 1条连线，使得各边权值最⼩for(int i = 1; i < G.numVertexes; i++) {min = INF, j = 1, k = 0;//寻找 V-U到 U的最⼩权值minfor(j; j < G.numVertexes; j++) {// lowcost[j] != 0保证顶点在 V-U中，⽤k记录此时的最⼩权值边在 V-U中顶点的下标if(lowcost[j] != 0 && lowcost[j] < min) {min = lowcost[j];k = j;}}}printf("V[%d]-V[%d] weight = %d\n", arjvex[k], k, min);lowcost[k] = 0; //表⽰将Vk纳⼊ U//查找邻接矩阵Vk⾏的各个权值，与lowcost的对应值进⾏⽐较，若更⼩则更新lowcost，并将k存⼊arjvex数组中for(int i = 1; i < G.numVertexes; i++) {if(lowcost[i] != 0 && G.arc[k][i] < lowcost[i]) {lowcost[i] = G.arc[k][i];arjvex[i] = k;}}}int main() {MGraph *G = (MGraph *)malloc(sizeof(MGraph));CreateMGraph(G);MiniSpanTree_Prim(*G);}/*input:4 5abcd0 1 20 2 20 3 71 2 42 3 8output:V[0]-V[1] weight = 2V[0]-V[2] weight = 2V[0]-V[3] weight = 7最⼩总权值: 11*/时间复杂度O(n^2)克鲁斯卡尔算法（Kruskal算法）思路：以边为⽬标进⾏构建最⼩⽣成树在边集中依次寻找最⼩权值边，若构建是不形成环路（利⽤parent数组记录各点的连通分量），则将其添加到最⼩⽣成树中。

克鲁斯卡尔算法的原理-回复克鲁斯卡尔算法是一种用于解决最小生成树（Minimum Spanning Tree，简称MST）问题的贪婪算法。

在图论中，最小生成树是图的所有顶点连接形成的一棵树，该树的所有边的权重之和最小。

克鲁斯卡尔算法的主要原理是通过不断选择图的最小权重边，逐步构建最小生成树。

重复以下步骤直到形成最小生成树：1. 创建一个空集合，用于存储最小生成树的边。

2. 对图的所有边按照权重进行排序。

3. 从最小权重的边开始，逐个考虑每条边：a. 如果将该边添加到最小生成树中不会形成环路，则将其添加到最小生成树的边集合中。

b. 如果该边会形成环路，则放弃该边并考虑下一条边。

4. 重复步骤3直到最小生成树的边集合包含了图的所有顶点，即所有顶点都被连接。

下面我们逐一解析克鲁斯卡尔算法的原理步骤。

步骤1：创建一个空集合，用于存储最小生成树的边。

这个集合被称为最小生成树的边集合。

开始时，它是一个空集合，没有任何边。

步骤2：对图的所有边按照权重进行排序。

对图中的所有的边按照权重进行升序排列。

这样可以保证在后续步骤中，我们总是选择最小权重的边。

步骤3.1：从最小权重的边开始，逐个考虑每条边。

从排序后的边集合中，选择权重最小的边开始考虑。

步骤3.2：如果将该边添加到最小生成树中不会形成环路，则将其添加到最小生成树的边集合中。

为了判断是否会形成环路，我们可以使用并查集数据结构。

并查集可以帮助我们快速判断两个顶点是否属于同一个连通分量。

如果两个端点属于同一个连通分量，则添加这条边会形成环路，所以我们需要放弃这条边。

如果两个端点不属于同一个连通分量，我们可以将这条边添加到最小生成树的边集合中，并合并两个连通分量。

步骤3.3：如果该边会形成环路，则放弃该边并考虑下一条边。

如果判断添加该边会形成环路，则放弃这条边，考虑下一条边。

步骤4：重复步骤3直到最小生成树的边集合包含了图的所有顶点。

重复进行步骤3，直到最小生成树的边集合中包含了图的所有顶点。

Kruskal算法(克鲁斯卡尔算法)Python代码简介K r us ka l算法是一种用于解决最小生成树问题的贪心算法。

它通过逐步选择边，将未连接的顶点逐渐合并成一个连通分量，并且保证最后形成的树中不会出现环。

本文将介绍K ru sk al算法的基本思想及其在Py th on 中的实现。

算法原理K r us ka l算法的基本思想是将图的所有边按照权重（即边的长度）从小到大进行排序，然后逐条选择边，并判断是否会形成环。

如果不会形成环，则将该边加入最小生成树中，直到最小生成树的边数等于节点数减一为止。

算法步骤1.根据图的边的权重进行排序。

2.初始化一个空的最小生成树列表，用于存放已选择的边。

3.初始化一个空的并查集，用于判断边的端点是否已经在同一个连通分量中。

4.遍历排序后的边，对于每一条边：-判断边的两个端点是否已经在同一个连通分量中，如果不在，将该边加入最小生成树列表，并将边的两个端点合并到同一个连通分量中。

5.返回最小生成树列表作为最终的生成树。

Pytho n实现下面是使用P yt ho n实现Kr us ka l算法的代码：c l as sU ni on Fi nd:d e f__i ni t__(se lf,n):s e lf.p ar en t=li st(r an ge(n))s e lf.r an k=[0]*nd e ff in d(se lf,x):i f se lf.p ar en t[x]!=x:s e lf.p ar en t[x]=se l f.fi nd(s el f.par e nt[x]) r e tu rn se lf.p ar ent[x]d e fu ni on(s el f,x,y):r o ot_x,r oo t_y=sel f.f in d(x),s el f.f i nd(y) i f ro ot_x!=ro ot_y:i f se lf.r an k[ro ot_x]>se lf.r an k[roo t_y]:s e lf.p ar en t[ro ot_y]=ro ot_xe l se:s e lf.p ar en t[ro ot_x]=ro ot_yi f se lf.r an k[ro ot_x]==s el f.ra nk[ro o t_y]: s e lf.r an k[ro ot_y]+=1d e fk ru sk al(g ra ph):e d ge s=[]f o ri,r ow in en um era t e(gr ap h):f o rj,c os ti ne nu mer a te(r ow):e d ge s.ap pe nd((cos t,i,j))e d ge s.so rt()n u m_no de s=le n(gra p h)t r ee=[]u n io n_fi nd=U ni onF i nd(n um_n od es)f o rc os t,i,ji ne dge s:i f un io n_fi nd.f ind(i)!=un io n_fi nd.f in d(j):u n io n_fi nd.u ni on(i,j)t r ee.a pp en d((i,j))r e tu rn tr ee使用示例为了更好地理解K rus k al算法的实现，下面给出一个使用示例：构建图的邻接矩阵表示g r ap h=[[0,2,3,1],[2,0,0,4],[3,0,0,5],[1,4,5,0]]使用Kruskal算法计算最小生成树m i ni mu m_sp an ni ng_t re e=kr us ka l(gra p h)输出最小生成树的边f o re dg ei nm in im um_s pa nn in g_tr ee:p r in t(ed ge)输出结果为：(0,3)(0,1)(1,0)总结K r us ka l算法是一种高效的求解最小生成树问题的算法。

克鲁斯卡尔算法的时间复杂度
克鲁斯卡尔算法是一种用于在给定图中寻找最小权重路径的最
先进的算法。

本文将对克鲁斯卡尔算法的时间复杂度进行讨论，其中包括对克鲁斯卡尔算法每步操作的时间开销以及尝试找到整个图中
最小权重路径的总时间复杂度。

克鲁斯卡尔算法的每步操作的时间复杂度
克鲁斯卡尔算法的每步操作的时间复杂度取决于图中可用边的
数量。

对于一个具有N个顶点和E个边的图，每次操作的时间复杂度为O(E)，因此总的时间复杂度也是O(E)。

克鲁斯卡尔算法是一种基于贪婪法的算法，它试图找到整个图中最小权重路径。

在每一步操作中，它都会从可用边中选择具有最小权重的边，然后将其加入最终结果中。

整个算法的时间复杂度
最坏情况下，克鲁斯卡尔算法试图找到整个图中最小权重路径，而这需要尝试每一条可能的路径。

因此，如果每一步操作的时间复杂度为O(E)，那么整个算法的时间复杂度将是O(E^2)。

此外，如果图中的边的数量变多，克鲁斯卡尔算法的效率也会变得越来越低，因为它需要在每一步操作中尝试多个边并尝试其最小权重值。

优化
为了提高克鲁斯卡尔算法的效率，可以采用“最小堆”数据结构。

最小堆可以帮助开发人员以O(logE)的时间复杂度快速查找和修改权
重最小的边，从而将最终算法的时间复杂度从O(E^2)降低到
O(ElogE)。

结论
克鲁斯卡尔算法是一种非常有效的算法，它可以在解决图论问题时帮助开发人员找到最小权重路径。

在最坏的情况下，算法的时间复杂度为O(E^2)，但是可以通过采用最小堆数据结构将其降低到
O(ElogE)。

普里姆算法和克鲁斯卡尔算法在计算机科学中，图是一种常见的数据结构，它由顶点和边组成。

在图中，顶点代表对象，边代表对象间的关系。

因此，图的算法是计算机科学中的一个重要分支。

其中，普里姆算法和克鲁斯卡尔算法是两种常用的最小生成树算法。

一、普里姆算法普里姆算法是一种基于贪心策略的算法，用于查找连接给定图中所有顶点的最小生成树。

该算法的基本思想是从一个起始顶点开始，逐步地添加新的顶点，直到所有顶点都被覆盖。

具体步骤如下：1. 选择一个起始顶点，并将其标记为已访问。

2. 查找与已访问顶点相邻的未访问顶点中，权值最小的边。

3. 将该边与对应的顶点标记为已访问，并将边加入最小生成树中。

4. 重复步骤2和步骤3，直到所有顶点都被访问。

二、克鲁斯卡尔算法克鲁斯卡尔算法也是一种基于贪心策略的算法，用于查找连接给定图中所有顶点的最小生成树。

该算法的基本思想是将边按照权值从小到大排序，逐步地将边加入最小生成树中，直到所有顶点都被覆盖。

具体步骤如下：1. 将图中所有边按照权值从小到大排序。

2. 逐步地将边加入最小生成树中，直到所有顶点都被覆盖。

3. 在加入新边的过程中，如果新边连接的两个顶点已经在最小生成树中，那么不加入该边。

三、普里姆算法和克鲁斯卡尔算法的比较虽然普里姆算法和克鲁斯卡尔算法都可以用于查找连接给定图中所有顶点的最小生成树，但它们的实现方式有所不同。

普里姆算法的实现方式比较简单，适用于边稠密的图。

该算法的时间复杂度为O(n^2)，其中n为顶点数。

克鲁斯卡尔算法的实现方式较为复杂，适用于边稀疏的图。

该算法的时间复杂度为O(elog2e)，其中e为边数。

四、总结普里姆算法和克鲁斯卡尔算法都是常用的最小生成树算法。

它们的实现方式有所不同，适用于不同类型的图。

在实际应用中，需要根据图的特点选择合适的算法。

克鲁斯卡尔算法步骤克鲁斯卡尔算法是用来求加权连通图的最小生成树的一种算法，下面我就来给你详细说说它的步骤哦。

一、基本动作要领1. 首先呢，我们要把图中所有的边按照权值从小到大的顺序进行排序。

就像是把一群小朋友按照身高从矮到高排队一样，权值小的边就排在前面。

这是很重要的一步，因为整个算法就是从权值最小的边开始选择的。

2. 然后我们要创建一个空的边集合，用来存放那些将成为最小生成树的边。

这个边集合就像是一个小篮子，我们要慢慢把合适的边放进这个“篮子”里。

3. 接下来，我们就从排好序的边列表里，按照顺序一条一条地挑边。

对于每一条边呢，我们要看看把它加到我们的最小生成树（也就是那个存放边的集合）里会不会形成环。

这里就是一个关键啦，千万不能形成环啊。

比如说如果有三个顶点A、B、C，要是已经有边AB和BC在集合里了，那再加入边AC的话就会形成一个环，这种边是不能要的，这时候就得忽略这条边，继续去看后面的边。

这一步我之前就做错过呢，当时没注意环的问题，搞出来的结果就完全不对了。

二、个人小技巧对了，这里可以在判断是否形成环的时候用并查集的数据结构来简化这个操作。

并查集就像是一个快速判断家族关系的工具，如果两个顶点在同一个集合里（也就是有相同的祖先），那就说明再加上连接它们的边就会形成环。

这个方法真的会让整个过程简单很多呢。

我一开始不知道用并查集，每次判断环都要去遍历已经选好的边，那可真是太麻烦了。

三、容易忽视的细节在检查边的时候啊，一定要细心。

有时候图中的边可能会有重复的权值，不要只看到第一个权值相同的边就觉得可以了，要把所有权值相同的边都按照正常的流程检查一遍，看看是否能加入到最小生成树的边集合里。

我之前就以为只要找到了一个权值最小的边就大功告成了，结果忽略了还有其他相同权值的边可能也符合条件，导致得出了错误的最小生成树。

四、常见问题一个常见的问题就是对图的顶点和边的编号会混乱。

比如说你在纸上画一个图，可能一开始边画得乱七八糟的，或者顶点编号也不规律，那在排序边的时候可能就容易搞错。

克鲁斯卡尔算法求最小生成树的最短路径克鲁斯卡尔算法的核心思想是从图的边集中选取边来构建最小生成树，首先将图中的所有边按照权重进行排序。

然后依次取最小权重的边，如果这条边的加入不会形成环路，则将它加入最小生成树的边集中。

重复这个过程，直到最小生成树中的边数等于顶点数减一，或者所有的边都已经考虑过。

假设有一个包含n个顶点的带权无向图G=(V,E)，其中，V表示顶点的集合，E表示边的集合。

假设我们要求解G的最小生成树。

1.初始化边集E'为空集，集合S={v}，v是图中任意一个顶点。

2.对所有的边进行排序，按照边的权重从小到大排列。

3.从排序后的边集中依次选取边e，如果边e的两个顶点都不在集合S中，则将边e加入集合S，并加入边集E'中。

4.重复步骤3，直到E'中的边数等于n-1在克鲁斯卡尔算法中，需要使用并查集来判断选定的边e是否会形成环路。

并查集是一种数据结构，用于维护元素的等价关系。

它有两个主要操作，即查找和合并。

使用并查集的步骤如下：1.初始化并查集，使得每个元素都是一个单独的集合。

2.对每一条边e=(u,v)，如果u和v在同一个集合中，则说明加入这条边会形成环路；否则，将这两个集合合并。

3.重复步骤2，直到所有的边都考虑过。

接下来，我们通过一个具体的例子来说明克鲁斯卡尔算法的具体过程。

假设有以下的带权无向图G=(V,E)，其中，V={A,B,C,D,E,F,G}，E为边的集合，每条边的权重如下：AE:5AB:7AG:8BF:7BC:9CD:5CG:9DE:15DF:6EG:11EF:8FG:9按照权重对边进行排序：CD:5AE:5DF:6AB:7BF:7EF:8AG:8CG:9BC:9FG:9DE:15EG:11从最小的边开始选取，首先选取CD:5，加入到最小生成树的边集中。

最小生成树的边集：{"CD:5"}接下来选取AE:5，加入到最小生成树的边集中。