文档介绍：该【最小生成树求解方法与分析课件】是由【yzhlyb】上传分享，文档一共【16】页，该文档可以免费在线阅读，需要了解更多关于【最小生成树求解方法与分析课件】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。最小生成树求解方法与分析
报告人:
小组成员:
求解最小生成树方法
Prim算法
Kruskal算法
破圈法
三种算法的比较
Prim算法
基本思路:任选一个定点V0,连接于V0最近的顶点V1,得到子树T1,在连接与T1最近的顶点V2,得到子树T2,如此继续下去,直到所得子树包含所有顶点。
时间复杂度:O(n2),n为图的定点数。
Prim算法的抽象描述
PrimMST(G,T,r)
{//求图G的以r为根的MST,结果放在T=(U,TE)中
InitCandidateSet(„);
//初始化:设置初始的最短边候选集,并置T=({r},￠)
for(k=0;k<n-1;k++)
{//求n-1条树边
(u,v)=SelectLiShtEdge(„);
//选取最短边(u,v);
T←T∪{(u,v)};//扩充T
ModifyCandidateSet(„);
}
}
kruskal算法
基本思路:假设连通网N=(V,{E}),则令最小生成树的初始状态为只有n个顶点而无边的非连通图T=(V,{}),图中每个顶点自成一个连通分量。在E中选择一个代价最小的边,若该边依附的顶点落在T中不同的连通分量上,则将此边加入到T中,否则舍弃此边选择下一条代价最小的边。以此类推,直至T中所有顶点都在同一连通分量上。
Kruskal算法构造最小生成树过程
Kruskal算法的抽象描述
KruskalMST(G)
{//求连通网G的一棵MST
T=(V,￠);//初始化,T是只含n个顶点不包含边的森林依权值的递增序对E(G)中的边排序,并设结果在E[0..e-1]中
for(i=0;i<e;i++)
{//e为图中边总数取E[0..e-1)中的第i条边(u,v);
ifu和v分别属于T中两棵不同的树then
T=T∪{(u,v)};//(u,v)是安全边,将其加入T中
ifT已是一棵生成树then
returnT;
}//endforreturnT;
}
破圈法构造最小生成树过程
三种算法的比较
2、Kruskal算法是从空图出发,由生成森林到生成树。它是精确算法,即每次都能求得最优解,但对于规模较大的最小生成树问题,求解速度较慢,时间复杂度为0(eloge)(e为网中边数),适合于求边稀疏的网的最小生成树。