最小生成树PPT演示最终

讨论课题：最小生成树的求解方法与分析点击添加文本点击添加文本点击添加文本点击添加文本目录背景知识组内成员分工介绍最小生成树的求解方法与分析010203点击添加文本点击添加文本点击添加文本点击添加文本组内成员及分工介绍：

组长刘先喆：编写最小生成树求解方法、回答问题

组员陈静：汇报演讲、制作PPT

组员何安琪：制作PPT、分析算法、探索其他解决方法

组员韩佳文：撰写报告提问问题

组员李昕翼：撰写报告提问问题最小连接问题交通网络中，常常关注能把所有站点连接起来的生成树，使得该生成树各边权值之和为最小。例如：假设要在某地建造5个工厂，拟修筑道路连接这5处。经勘探，其道路可按无向边铺设。现在每条边的长度已经测出并标记在对应边上，如果我们要求铺设的道路总长度最短，如何铺设？背景知识最小生成树：在连通边赋权图G中求一棵总权值最小的生成树。该生成树称为最小生成树或最小代价树。构造最小生成树的思想构造最小生成树可以有多种算法。其中多数算法利用了最小生成树的一种简称为MST的性质：假设N=(V,{E})是一个连通网(v代表顶点集，E代表边集)，U是顶点集V的一个非空子集。若(u,v)是一条具有最小权值的边，其中u∈U，v∈V-U,则必存在一棵包含边(u,v)的最小生成树。点击添加文本点击添加文本点击添加文本点击添加文本普里姆算法克鲁斯卡尔构造算法最小生成树普里姆算法从连通网N={V,E}中的某一顶点U0出发，选择与它关联的具有最小权值的边(U0,v)，将其顶点加入到生成树的顶点集合U中。以后每一步从一个顶点在U中，而另一个顶点不在U中的各条边中选择权值最小的边(u,v),把它的顶点加入到集合U中。如此继续下去，直到网中的所有顶点都加入到生成树顶点集合U中为止普里姆算法利用该图按普里姆算法构造一棵最小生成树V3V2V1V4V5V65515666423V1V2V5V4V6V36513246556

iclosedgev2v3v4v5v6UV-Ukadjvexlowcost61V15V3V1V1V1615{V1}{V2,V3,V4,V5,V6}v3V1V2V5V4V6V36513246556

iclosedgev2v3v4v5v6UV-Ukadjvexlowcost51V15V3V3V1505{V1,V3}{V2,V4,V5,V6}v6V36V3464V3V6V1V2V5V4V6V36513246556

iclosedgev2v3v4v5v6UV-Ukadjvexlowcost004625V6V465v4V62V3V3{V1,V3,V6}{V2,V4,V5}V1V2V5V4V6V36513246556

iclosedgev2v3v4v5v6UV-Ukadjvexlowcost0002V4V3556V36{V1,V3,V6,V4}{V2,V5}v2V2V1V2V5V4V6V36513246556

iclosedgev2v3v4v5v6UV-Ukadjvexlowcost00005V2{V1,V3,V6,V4,V2}{V5}v53V23V5V1V2V5V4V6V36513246556

iclosedgev2v3v4v5v6UV-Ukadjvexlowcost000003V5{V1,V3,V6,V4,V2,v5}{}普里姆核心算法//用普里姆算法从第u个顶点出发构造网G的最小生成树T,输出T的各条边voidMiniSpanTree_PRIM(MGraphG,VertexTypeu){ inti,j,k; Closedgeclosedge; k=LocateVex(G,u); for(j=0;j<G.vexnum;++j)//辅助数组初始化 { if(j!=k) { strcpy(closedge[j].adjvex,u); closedge[j].lowcost=G.arcs[k][j].adj; } }..\..\普里姆算法\普里姆.cpp

closedge[k].lowcost=0;//初始时,U={u} printf("最小代价生成树的各条边为:\n"); for(i=1;i<G.vexnum;++i) {//选择其余G.vexnum-1个顶点 k=MiniNum(closedge,G);//求出T的下一个结点：第K顶点 printf("(%s-%s)%d\n",closedge[k].adjvex,G.vexs[k],closedge[k].lowcost);//输出生成树的边 closedge[k].lowcost=0;//第K顶点并入U集 for(j=0;j<G.vexnum;++j) if(G.arcs[k][j].adj<closedge[j].lowcost) { //新顶点并入U集后重新选择最小边 strcpy(closedge[j].adjvex,G.vexs[k]); closedge[j].lowcost=G.arcs[k][j].adj; } }}普里姆算法分析假设网中有n个顶点，则第一个进行初始化的循环语句的频度为n，第二个循环语句的频度为n-1；其中有两个内循环：其一是在closedge[v].lowcost中求最小值，其频度为n-1;其二是重新选择具有最小代价的边，其频度为n。由此，普里姆算法的时间复杂度为O(n²),与网中的边数无关，因此适用于求边稠密的网的最小生成树。克鲁斯卡尔算法克鲁斯卡尔算法从另一途径求网的最小生成树。假设连通网N=(V,{E}),则令最小生成树的初始状态为只有n个顶点而无边的非连通图T=(V,{}),图中每个顶点自成一个连通分量。在E中选择代价最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入到T中，否则舍去此边而选择下一条代价最小的边。以此类推，直至T中所有顶点都在同一连通分量上为止。克鲁斯卡尔算法利用该图按克鲁斯卡尔算法构造一棵最小生成树V3V2V1V4V5V65515666423各边权值的堆排

12345678910edgecost6155356426adjvexv1,v2v1,v3v1,v4v3,v4v2,v5v2,v3v3,v5v3,v6v4,v6v5,v66156325564

12345678910edgecost1234555666adjvexv1,v3v4,v6v2,v5v3,v6v3,v4v2,v3v1,v4v3,v5v5,v6v1,v2利用堆排序后结果：V1V3V2V5V6V41636625554

123456edgecost123455adjvexv1,v3v4,v6v2,v5v3,v6v3,v4v2,v31V1V3V2V5V6V41636625554

123456edgecost123455adjvexv1,v3v4,v6v2,v5v3,v6v3,v4v2,v32V1V3V2V5V6V41636625554

123456edgecost123455adjvexv1,v3v4,v6v2,v5v3,v6v3,v4v2,v33V1V3V2V5V6V41636625554

123456edgecost123455adjvexv1,v3v4,v6v2,v5v3,v6v3,v4v2,v34V1V3V2V5V6V41636625554

123456edgecost123455adjvexv1,v3v4,v6v2,v5v3,v6v3,v4v2，v35V1V3V2V5V6V41636625554

123456edgecost123455adjvexv1,v3v4,v6v2,v5v3,v6v3,v4v2,v35克鲁斯卡尔核心算法for(i=0;i<G.vexnum;i++)//各顶点集初始化 flag[i]=i; for(i=G.arcnum,count=1;count<G.vexnum;i--) { j=G.arcs[i].v1;k=G.arcs[i].v2; if(flag[j]!=flag[k])//两个点属于不同集合 { printf("(%s-%s)%d\n",G.vexs[j],G.vexs[k],G.arcs[i].value); count++; for(l=0;l<G.vexnum;l++) if(flag[l]==flag[k])//将点k所在集合的点并入j所在集合 flag[l]=flag[j]; } }

..\..\克鲁斯卡尔算法\最小生成树.cpp克鲁斯卡尔算法分析该算法至多对e条边各扫描一次，则每次选择最小代价的边仅需O(loge)的时间（第一次需O(e)）。又生成树T的每个连通分量可以看成是一个等价类，则构造T加入新的边的过程类似于求等价类的过程，构造T的过程仅需O(eloge)的时间，由此，克鲁斯卡尔算法的时间复杂度为O(eloge)。点击添加文本点击添加文本点击添加文本点击添加文本Solin算法Rosenstiehl和管梅谷算法Dijkstra算法最小生成树的其他求解方法Solin算法

此算法的基本思路是：将求连通带权图的最小生成树的过程分为若干阶段，每一阶段选取若干条边。具体步骤如下：（1）将每个顶点视为一棵树，图中所有顶点视为一个森林；（2）为每棵树选取一条边，它是该树与其他树相连的所有边中权值最小的