首页 > 编程知识 正文

克鲁斯卡尔算法求解过程,用克鲁斯卡尔求最小生成树

时间:2023-05-05 01:29:11 阅读:157107 作者:1

提供联络网:

ZZDDS(kruskal )算法的基本思想是假设n=(v,{E} )是连通网。

将最小生成树的初始状态作为只有n个顶点且没有边的非连接图T={V,{},图表中的各顶点都有一个连接成分。 在e中选择成本最低的边,如果该边的两个顶点位于t的不同连接分量上,则将该边添加到t。 否则,截断边,然后选择成本较小的边。 这样,直到t的所有顶点都在同一连接分量上。zzdds算法主要针对边展开,边数少的情况下效率非常高,因此对稀疏图有很大的好处;

另一方面,普里姆算法是密集图,即在边数非常多的情况下更好。

图解1、将连接网的边缘变换为边缘集合数组,按权重从小到大的顺序对它们进行排序。

2、去掉所有边,得到T={A,b,c,d,e,f,g,h,I,{}。

3、循环扫描对边集合群,开始时,i=0,找到第一边,两个顶点为e和h,分别属于两棵树(两个连通分量),所以t=(a,b,c,d,e,f,g,h,I,h )

4、i=1,找到第二条边,两个顶点为c和I,分别属于两棵树(两个连通分量),所以t=(a,b,c,d,e,f,g,h,I,) (e,h ),c

5、i=2,找到第三条边,两顶点为a和b,分别属于两棵树(两个连接成分),所以t=(a,b,c,d,e,f,g,h,I,) (e,h )、c,I )

6、i=3,找到第四条边,两顶点为a和f,分别属于两棵树(两个连通分量),所以t=(a、b、c、d、e、f、g、h、I、) (e、h )、c、

7,I=4,找到第五条边,两个顶点为b和I,分别属于两棵树(两个连接成分),所以t=(a,b,c,d,e,f,g,h,I,) ) e,h ),c

8,I=5,找到第六条边,两个顶点为d和h,分别属于两棵树(两个连通分量),所以t=(a,b,c,d,e,f,g,h,I,) (e,h ),c

9、I=找到第6、7条边,2个顶点为b和g,分别属于2棵树(2个连接成分),所以t=(a、b、c、d、e、f、g、h、I、) (e、h )、c、c、

10、i=7,找到第八条边,两顶点是g和f,它们属于同一棵树,扔掉。 找i=8,两个顶点是b和c,它们属于同一棵树,扔掉。 进而寻找i=9的话,2个顶点是g和h,因为分别属于2棵树(2个连通成分),所以t=(a,b,c,d,e,f,g,h,I,) (e,h ),c,I ),a

11、所有后续循环导致循环,最终最小生成树为:

时间复杂度寻找边缘的两个顶点是否属于同一树的时间复杂度为o(loge ),外侧有for循环e次。 因此,zzdds算法的时间复杂度是o(eloge ) (escrip ttype=' math/tex ' id=' math jax-element-110 ' e/script表示边的数量) )。

版权声明:该文观点仅代表作者本人。处理文章:请发送邮件至 三1五14八八95#扣扣.com 举报,一经查实,本站将立刻删除。