kruskal算法时间复杂度

Ⅰ kruskal算法是什么

kruskal算法是：克鲁斯卡尔算法。禅缓是求连通网的最小生成树的另一种方法。与普里姆算法不同，它的时间复杂度为O（eloge）、（e为网中的边数）租袭野，所以，适合于求边稀疏的网的最小生成树。

克鲁斯卡尔（Kruskal）算法从另一途径求网的最小生成树。其基本思想是：假设连通网G=（V，E），令最小生成树的初始状态为只有n个顶点而无边的非连通图T=（V，{}），概述图中每个顶点自成一个连通分量。

在E中选择代价最小的边，若该边依附的顶点分别在T中不同的连通分量上，则将此边加入到T中；否则，舍去此边而选择下一条代价最小的边。依此类推，直至T中所有顶点构成一个连通分量为止。

复杂度：

克鲁斯卡尔算法的时间复杂度主要由排序方法决定，而克鲁斯卡尔算法的排序方法只与网中边的条数有关，而与网中顶点的个数无关，当使用时间复杂度为O（elog2e）的排序方法时，克鲁斯卡尔算法的时间复杂度即为O（log2e），因此当网的顶点个数较多、而边的条数较少时，使用克鲁斯卡尔算法构造最小生成弊喊树效果较好。

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

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

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

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

(2)kruskal算法时间复杂度扩展阅读：

克鲁斯卡尔算法证明

假设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)。

Ⅲ 数据结构（十）：最小生成树

最小生成树是带权无向连通图中权值最小的生成树，根据 图 中生成树定义可知， 个顶点的连通图中，生成树中边的个数为 ，向生成树中添加任意一条边，则会形成环。生成树存在多种，其中权值之和最小的生成树即为最小生成树。

若 为最小生成树 的一个真子集，即 的顶点集合和边集合都是 的顶点和边集合的子集，构造最小生成树过程为向 中添加顶点和边，添加的原则有两种：

kruskal 算法即为上述第一种原则，通过选择图中的最小权值边来构造最小生成树，过程中需要注意避免形成环。

step 1：
最小权值边为顶点 7、8 形成的边

step 2：
最小权值边为顶点 3、9 形成的边

step 3：
最小权值边为顶点 6、7 形成的边

step 4：
最小权值边为顶点 3、6 形成的边

step 5：
最小权值边为顶点 1、2 形成的边

step 6：
最小权值边为顶点 3、4 形成的边

step 7：
最小权值边为顶点 1、8 形成的边

step 8：
最小权值边为顶点 4、5 形成的边

最小生成树的权值之和为 37

这里使用邻接表作为图的存储结构

这里使用 getEdgesFromAdjacencyList 函数完成邻接表到边集合的转换，使用快排 sort 完成对边集合的排序，使用 origin 函数返回每个子图的根。

该函数返回顶点 index 所属子图的根顶点，其中 vertices[index] 位置上存储的是顶点 index 的上一个顶点，每个子图中，根顶点的上一个顶点为自身。

kruskal 算法中使用 getEdgesFromAdjacencyList 函数完成邻接表向边集合的转换，函数内部存在两层循环，访问邻接表中每个顶点的相邻顶点，复杂度为 。使用快排对边集合进行排序，时间复杂度为 ，因为 ，所以快排时间复杂度可以表述为 。 kruskal 算法中 while 循环取最小权值边，并对边的两个顶点执行 origin 函数判断是否属于同一个子图，时间复杂度为 。所以 kruskal 算法的时间复杂度为 。

kruskal 算法的过程为不断对子图进行合并，直到形成最终的最小生成树。 prim 算法的过程则是只存在一个子图，不断选择顶点加入到该子图中，即通过对子图进行扩张，直到形成最终的最小生成树。

step 1：
距离子图的最近顶点为 4

step 2：
距离子图的最近顶点为 3

step 3：
距离子图的最近顶点为 9

step 4：
距离子图的最近顶点为 6

step 5：
距离子图的最近顶点为 7

step 6：
距离子图的最近顶点为 8

step 7：
距离子图的最近顶点为 2

step 8：
距离子图的最近顶点为 1

最小生成树的权值之和为 37

这里使用邻接表作为图的存储结构

这里使用 vertices 列表存储每个顶点元素，每个元素包括两个属性， index 为顶点下标， weight 为顶点距离子图的大小。算法中使用 verticesIndex 列表存储每个顶点元素在 vertices 列表中的下标位置。使用 heapSort 堆排序对每个顶点到子图的距离进行排序，即对 vertices 列表进行排序，使用堆排序内的 transformToHeap 函数调整 vertices 列表为小顶堆。当添加新顶点到子图后，使用 updateVertices 函数完成对相邻顶点的距离更新。

当 vertices 列表调整为小顶堆之后，将列表首、尾元素交换，则列表尾元素即为距离子图最近的顶点元素。

对每一个相邻顶点，如果不在子图中，则判断是否更新到子图的距离。更新距离后的 while 循环操作，目的为调整堆结构为小顶堆。

prim 算法中构造顶点列表的时间复杂度为 。使用堆排序对顶点列表进行排序，时间复杂度为 。 prim 算法中 while 循环取最近顶点元素，并调整元素取出后列表的堆结构，所以调整复杂度为 ；同时，循环结构内执行 updateVertices 函数，更新每个取出顶点的相邻顶点距离值，所以更新顶点数为 ，因为每个顶点更新距离后，需要调整堆结构为小顶堆，所以更新复杂度为 。所以 prim 算法的总时间复杂度为 。

Ⅳ 最小生成树两种算法有何区别

主要有两个：
1.普里姆（prim)算法
特点：时间复杂度为御老o(n2).适合于求边稠密镇森升的最小生成树。
2.克鲁斯卡尔（kruskal)算法
特点：时间复杂度为o(eloge)(e为网中边数），适合于春蔽求稀疏的网的最小生成树。