![](https://csdnimg.cn/release/download_crawler_static/32253287/bg1.jpg)
kruskal 算法
百科名片
K r u s k a l 算法每次选择 n- 1 条边,所使用的贪婪准则是: 从剩下的边中选择一条不会
产生环路的具有最小耗费的边加入已选择的边的集合中。 注意到所选取的边若产生环路则不
可能形成一棵生成树。 K r u s k a l 算法分 e 步,其中 e 是网络中边的数目。按耗费递
增的顺序来考虑这 e 条边,每次考虑一条边。当考虑某条边时,若将其加入到已选边的集
合中会出现环路,则将其抛弃,否则,将它选入。
目录 [隐藏 ]
Kruskal 算法
普里姆算法 (prim 算法)
Kruskal 算法
普里姆算法 (prim 算法)
[编辑本段 ]
Kruskal 算法
算法定义
克鲁斯卡尔算法
假设 WN=(V,{E}) 是一个含有 n 个顶点的连通网,则按照克鲁斯卡尔算法构造
最小生成树的过程为:先构造一个只含 n 个顶点,而边集为空的子图,若将该子图
中各个顶点看成是各棵树上的根结点,则它是一个含有 n 棵树的一个森林。之后,
从网的边集 E 中选取一条权值最小的边,若该条边的两个顶点分属不同的树,则将
其加入子图,也就是说,将这两个顶点分别所在的两棵树合成一棵树;反之,若该条
边的两个顶点已落在同一棵树上,则不可取,而应该取下一条权值最小的边再试之。
依次类推,直至森林中只有一棵树,也即子图中含有 n-1 条边为止。
举例描述
初始时没有任何边被选择。边( 1 , 6)是最先选入的边,它被加入到欲构建的
生成树中,得到图 1 3 - 1 2 c 。下一步选择边( 3 ,4 )并将其加入树中(如图 1
3 - 1 2 d 所示)。然后考虑边 ( 2, 7 ,将它加入树中并不会产生环路,于是便得
到图 1 3 - 1 2 e。下一步考虑边( 2, 3)并将其加入树中(如图 1 3 - 1 2 f 所
示)。在其余还未考虑的边中,( 7,4 )具有最小耗费,因此先考虑它,将它加入正
在创建的树中会产生环路,所以将其丢弃。此后将边( 5, 4)加入树中,得到的树
如图 13-12g 所示。下一步考虑边( 7, 5 ),由于会产生环路,将其丢弃。最后考