克鲁斯卡尔算法的时间复杂度为多少
Kruskal算法的时间复杂度由排序算法决定，若采用快排则时间复杂度为O(N log N)。
kruskal算法：
求加权连通图的最小生成树的算法。kruskal算法总共选择n- 1条边，（共n个点）所使用的贪婪准则是：从剩下的边中选择一条不会产生环路的
具有最小耗费的边加入已选择的边的集合中。注意到所选取的边若产生环路则不可能形成一棵生成树。kruskal算法分e 步，其中e
是网络中边的数目。按耗费递增的顺序来考虑这e
条边，每次考虑一条边。当考虑某条边时，若将其加入到已选边的集合中会出现环路，则将其抛弃，否则，将它选入。
假设WN=(V,{E})是一个含有 n 个顶点的连通网，则按照克鲁斯卡尔算法构造最小生成树的
过程为：先构造一个只含 n 个顶点，而边集为空的子图，若将该子图中各个顶点看成是各棵树上的根结点，则它是一个含有 n
棵树的一个森林。之后，从网的边集 E
中选取一条权值最小的边，若该条边的两个顶点分属不同的树，则将其加入子图，也就是说，将这两个顶点分别所在的两棵树合成一棵树；反之，若该条边的两个顶
点已落在同一棵树上，则不可取，而应该取下一条权值最小的边再试之。依次类推，直至森林中只有一棵树，也即子图中含有 n-1条边为止。
不同的算法时间复杂度不一样，普里姆算法O(n^2)，克鲁斯卡尔算法O(eloge)
时间复杂度为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)。
参考资料来源：百度百科——克鲁斯卡尔算法
假设G=(V,E) 是一个具有n个顶点的连通网，T=(U,TE)是G的最小生成树，U的初值等于V，即包含有G中的全部顶点，TE的初值为空集。该算法的基本思想是：将图G中的边按权值从小到大的顺序依次选取，若选取的边使生成树T不形成回路，则把它并入TE中，保留作为T的一条边，若选取的边使生成树T形成回路，则将其舍弃，如此进行下去直到TE中包含n-1条边为止，此时的T即为最小生成树。
例如，按克鲁斯卡尔算法构造图7.12(a)的最小生成树的过程如图中(b)、(c)、...、(f)所示。在图(a)中，按权值递增顺序依次考虑边(1,3),(4,6),(2,5),(3,6),(1,4),(2,3),(3,5), (1,2),(5,6)和(3,4)，因为前四条边上的权值最小，而且又满足不在同一个连通分量上(不形成回路)的条件，所以依次将它们加入到T中。接着要考虑当前权值最小的边(1,4)，因该边的两个端点在同一个连通分量上(即形成回路)，故舍去这条边。然后再选择边(2,3)加入到T中，便得到要求的一棵最小生成树。
上述的克鲁斯卡尔算法，至多对e条边各扫描一次，每次选择最小代价的边仅需要O(loge)的时间。因此，克鲁斯卡尔算法的时间复杂度为O(eloge)。
由于一个网(带权图)中会有权值相同的边，所以从不同的顶点出发，可以得到不同的最小生成树。例如，在前例中的图(a)，如若从顶点v2出发，会得到一棵完全不同的MST。
克鲁斯卡尔算法的时间复杂度为O(eloge);
原灵复方： Kruskal算法的时间复杂度由排序算法决定,若采用快排则时间复杂度为O(N log N).kruskal算法:求加权连通图的最小生成树的算法.kruskal算法总共选择n- 1条边,(共n个点)所使用的贪婪准则是:从剩下的边中选择一条不会产生环路的 ...
黄梅县18485292640： 最小生成树的两种算法?图的最小生成树的两个主要算法是什么?它们各自的特点? - ？
原灵复方：[答案] 主要有两个: 1.普里姆(Prim)算法 特点:时间复杂度为O(n2).适合于求边稠密的最小生成树. 2.克鲁斯卡尔(Kruskal)算法 特点:时间复杂度为O(eloge)(e为网中边数),适合于求稀疏的网的最小生成树.
黄梅县18485292640： 最小生成树的两种算法? - ？
原灵复方： 主要有两个: 1.普里姆(Prim)算法 特点:时间复杂度为O(n2).适合于求边稠密的最小生成树. 2.克鲁斯卡尔(Kruskal)算法 特点:时间复杂度为O(eloge)(e为网中边数),适合于求稀疏的网的最小生成树.
黄梅县18485292640： 最小生成树 普里姆算法和克鲁斯卡尔算法 - ？
原灵复方： kruskal算法的时间复杂度主要由排序方法决定,其排序算法只与带权边的个数有关,与图中顶点的个数无关,当使用时间复杂度为O(eloge)的排序算法时,克鲁斯卡算法的时间复杂度即为O(eloge),因此当带权图的顶点个数较多而边的条数较少...
黄梅县18485292640： 克鲁斯卡尔算法的基本思想 - ？
原灵复方： 先构造一个只含 n 个顶点、而边集为空的子图,把子图中各个顶点看成各棵树上的根结点,之后,从网的边集 E 中选取一条权值最小的边,若该条边的两个顶点分属不同的树,则将其加入子图,即把两棵树合成一棵树,反之,若该条边的两个顶点已落在同一棵树上,则不可取,而应该取下一条权值最小的边再试之.依次类推,直到森林中只有一棵树,也即子图中含有 n-1 条边为止.时间复杂度为为O(e^2), 使用并查集优化后复杂度为 O(eloge),与网中的边数有关,适用于求边稀疏的网的最小生成树.
黄梅县18485292640： 某无向连通图具有n个顶点e条边,利用克鲁斯卡尔算法生成最小生成树...？
原灵复方： 标题: 最小生成树 时 限: 1000 ms 内存限制: 10000 K 总时限: 3000 ms 描述: 有一张城市地图,图中的顶点为城市,无向边代表两个城市间的连通关系,边上的权为在这两个城市之间修建高速公路的造价,研究后发现,这个地图有一个特...
