提供联络网:
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表示边的数量) )。