亲爱的网友们,相信很多人对kruskal算法和Kruskal算法的时间复杂度是多少都不是特别了解,因此今天我来为大家分享一些关于kruskal算法和Kruskal算法的时间复杂度是多少的知识,希望能够帮助大家解决这些问题。
本文目录一览
kruskal算法
kruskal算法指克鲁斯卡尔算法。
克鲁斯卡尔算法是求连通网的最小生成树的另一种方法。与普里姆算法不同,它的时间复杂度为O(eloge)(e为网中的边数),所以,适合于求边稀疏的网的最小生成树 。
克鲁斯卡尔(Kruskal)算法从另一途径求网的最小生成树。其基本思想是:假设连通网G=(V,E),令最小生成树的初始状态为只有n个顶点而无边的非连通图T=(V,{}),概述图中每个顶点自成一个连通分量。
在E中选择代价最小的边,若该边依附的顶点分别在T中不同的连通分量上,则将此边加入到T中;否则,舍去此边而选择下一条代价最小的边。依此类推,直至T中所有顶点构成一个连通分量为止。
克鲁斯卡尔算法的时间复杂度主要由排序方法决定,而克鲁斯卡尔算法的排序方法只与网中边的条数有关,而与网中顶点的个数无关,当使用时间复杂度为O(elog2e)的排序方法时,克鲁斯卡尔算法的时间复杂度即为O(log2e),因此当网的顶点个数较多、而边的条数较少时,使用克鲁斯卡尔算法构造最小生成树效果较好。
Kruskal算法的时间复杂度是多少?
Kruskal算法的时间复杂度由排序算法决定,若采用快排则时间复杂度为O(N log N)。kruskal算法:
求加权连通图的最小生成树的算法。kruskal算法总共选择n- 1条边,(共n个点)所使用的贪婪准则是:从剩下的边中选择一条不会产生环路的
具有最小耗费的边加入已选择的边的 中。注意到所选取的边若产生环路则不可能形成一棵生成树。kruskal算法分e 步,其中e
是网络中边的数目。按耗费递增的顺序来考虑这e
条边,每次考虑一条边。当考虑某条边时,若将其加入到已选边的 中会出现环路,则将其抛弃,否则,将它选入。
假设WN=(V,{E})是一个含有 n 个顶点的连通网,则按照克鲁斯卡尔算法构造最小生成树的
过程为:先构造一个只含 n 个顶点,而边集为空的子图,若将该子图中各个顶点看成是各棵树上的根结点,则它是一个含有 n
棵树的一个森林。之后,从网的边集 E
中选取一条权值最小的边,若该条边的两个顶点分属不同的树,则将其加入子图,也就是说,将这两个顶点分别所在的两棵树合成一棵树;反之,若该条边的两个顶
点已落在同一棵树上,则不可取,而应该取下一条权值最小的边再试之。依次类推,直至森林中只有一棵树,也即子图中含有 n-1条边为止。
如果您对本文的解答感到满意,请在文章结尾处点击“顶一下”以表示您的肯定。如果您对本文不满意,也请点击“踩一下”,以便我们改进该篇文章。