|
克鲁斯卡尔(Kruskal)算法 ()算法思想 ①T的初始状态 只有n个顶点而无边的森林T=(V￠ ) ②按边长递增的顺序选择E中的n安全边(uv)并加入T生成MST 注意 安全边指两个端点分别是森林T里两棵树中的顶点的边加入安全边可将森林中的两棵树连接成一棵更大的树 因为每一次添加到T中的边均是当前权值最小的安全边MST性质也能保证最终的T是一棵最小生成树 ()算法特点 该算法的特点是当前形成的集合T除最后的结果外始终是一个森林 ()Kruskal算法的抽象描述 KruskalMST(G){//求连通网G的一棵MST T=(V￠); //初始化T是只含n个顶点不包含边的森林 依权值的递增序对E(G)中的边排序并设结果在E[e]中 for(i=;i 取E[0..e-1)中的第i条边(u，v); if u和v分别属于T中两棵不同的树then T=T∪{(u，v)};//(u，v)是安全边，将其加入T中 if T已是一棵生成树then `` return T; }//endfor return T; } (4)用Kruskal算法构造最小生成树的过程 用Kruskal算法构造最小生成树的过程【 参见动画演示 】 (5)算法分析 该算法的时间复杂度为O(elge)。TW.wiNGwIT.CoM Kruskal算法的时间主要取决于边数。它较适合于稀疏图。 |
