克鲁斯卡尔

时间:2025-01-06 12:31:49编辑:阿奇

请用克鲁斯卡尔算法为下图构造最小生成树,谢谢。

克鲁斯卡尔算法的基本思想,这是我自己结合教材理解的,难免有误,谨慎参考:1:将图中的n顶点看成是n个集合。解释为,图中共有6个顶点,那么就有六个集合。即a,b,c,d,e,f各自分别都是一个集合。{a},{b}等。2:按权值由小到大的顺序选择边。所选边应满足两个顶点不在同一个顶点集合内。将该边放到生成树边的集合,同时将该边的两个顶点所在的集合合并。这是书上的描述,可能有点难理解,这里解释一下:首先,选择权值最小的边,即为图中的(a,c)边,此时a,c满足不在同一个顶点集合内,将这个边记录下来,然后合并这两个顶点的集合,即此时剩下五个顶点集合了,{a,c},{b},{d},{e},{f}3:重复步骤2,直到所有的顶点都在同一个集合内!解释如下:此时剩下的边中权值最小的为(d,f),满足不在同一个顶点集合,所以记录下该边,然后合并这两个顶点集合。新的顶点集合为{a,c} {b} {e} {d,f}接着,继续重复,选择边(b,e),满足不在同一个顶点集合内,所以记录下该边,然后再次合并这两个集合,新的集合为{a,c} {d,f} {b,e}继续,选择边(c,f),满足不在同一个顶点集合内,所以记录下该边,然后合并这两个顶点所在的集合,新集合为{a,c,d,f} {b,e}再继续,选择权值为15的边,发现边(c,d)和边(a,d)都不满足条件不在同一个顶点集合内,所以只能选择边(b,c),记录下该边,然后合并顶点集合,新集合为{a,b,c,d,e,f},此时所有点都在同一集合内,所以结束!4:将上面我们记录的那些边连接起来就行了!这就是最小生成树,附本人手绘:


克鲁斯卡尔时间复杂度怎么算出来的

Kruskal算法的时间复杂度由排序算法决定,若采用快排则时间复杂度为O(N log N)。

kruskal算法:

求加权连通图的最小生成树的算法。kruskal算法总共选择n- 1条边,(共n个点)所使用的贪婪准则是:从剩下的边中选择一条不会产生环路的
具有最小耗费的边加入已选择的边的集合中。注意到所选取的边若产生环路则不可能形成一棵生成树。kruskal算法分e 步,其中e
是网络中边的数目。按耗费递增的顺序来考虑这e
条边,每次考虑一条边。当考虑某条边时,若将其加入到已选边的集合中会出现环路,则将其抛弃,否则,将它选入。
假设WN=(V,{E})是一个含有 n 个顶点的连通网,则按照克鲁斯卡尔算法构造最小生成树的
过程为:先构造一个只含 n 个顶点,而边集为空的子图,若将该子图中各个顶点看成是各棵树上的根结点,则它是一个含有 n
棵树的一个森林。之后,从网的边集 E
中选取一条权值最小的边,若该条边的两个顶点分属不同的树,则将其加入子图,也就是说,将这两个顶点分别所在的两棵树合成一棵树;反之,若该条边的两个顶
点已落在同一棵树上,则不可取,而应该取下一条权值最小的边再试之。依次类推,直至森林中只有一棵树,也即子图中含有 n-1条边为止。


上一篇:亨利卢梭

下一篇:没有了