您好,欢迎访问三七文档
当前位置:首页 > 商业/管理/HR > 管理学资料 > 最小生成树求解方法与分析
最小生成树求解方法与分析报告人:小组成员:求解最小生成树方法•Prim算法•Kruskal算法•破圈法•三种算法的比较Prim算法•基本思路:任选一个定点V0,连接于V0最近的顶点V1,得到子树T1,在连接与T1最近的顶点V2,得到子树T2,如此继续下去,直到所得子树包含所有顶点。•时间复杂度:O(n2),n为图的定点数。Prim算法构造最小生成树过程Prim算法的抽象描述•PrimMST(G,T,r)•{//求图G的以r为根的MST,结果放在T=(U,TE)中•InitCandidateSet(„);•//初始化:设置初始的最短边候选集,并置T=({r},¢)•for(k=0;kn-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;ie;i++)•{//e为图中边总数取E[0..e-1)中的第i条边(u,v);•ifu和v分别属于T中两棵不同的树then•T=T∪{(u,v)};//(u,v)是安全边,将其加入T中ifT已是一棵生成树thenreturnT;}//endforreturnT;}•破圈法•基本思路:破圈法就是在带权图的回路中找出权值最大的边,将该边去掉,重复这个过程,直到图连通且没有圈为止,保留下来的边组成的图即为最小生成树。•时间复杂度:0(n3)破圈法构造最小生成树过程三种算法的比较1、prim算法同样是从空图出发,将点进行二分化,从而逐步加边得到最小生成树。它是近似求解算法,虽然对于大多数最小生成树问题都能求得最优解,但相当一部分求得的是近似最优解,具体应用时不一定很方便。但是它可以看作是很多种最小树算法的概括,在理论上有一定的意义。其时间复杂度为0(n2),于网中边数无关,因此适用于求边稠密的网的最小生成树。三种算法的比较•2、Kruskal算法是从空图出发,由生成森林到生成树。它是精确算法,即每次都能求得最优解,但对于规模较大的最小生成树问题,求解速度较慢,时间复杂度为0(eloge)(e为网中边数),适合于求边稀疏的网的最小生成树。三种算法的比较•破圈法是从图G出发,逐步去边破圈得到最小生成树。它最适合在图上工作,当图较大时,可以几个人同时在各个子图上工作,因此破圈法在实用上是很方便的。算法总的计算量为0(n3)。结束谢谢观看
本文标题:最小生成树求解方法与分析
链接地址:https://www.777doc.com/doc-5605075 .html