《最小生成树ppt课件》由会员分享，可在线阅读，更多相关《最小生成树ppt课件（20页珍藏版）》请在装配图网上搜索。
1、 tail head cost 边的两个顶点位置边的两个顶点位置 边的权值边的权值const int MAXINT=机器可表示的机器可表示的,问题中不可问题中不可 能出现的大数能出现的大数class MinSpanTree;class MSTEdgeNode /生成树边结点类定义生成树边结点类定义friend class MinSpanTree;private:int tail,head;/生成树各边的两顶点生成树各边的两顶点 float cost;/生成树各边的代价生成树各边的代价;class MinSpanTree /生成树的类定义生成树的类定义public:MinSpanTree(int
2、 sz=NumVertices-1):MaxSize(sz),n(0)edgevalue=new MSTEdgeNodeMaxSize;int Insert(MSTEdgeNode&item);/将将item加到最小生成树中加到最小生成树中protected:MSTEdgeNode*edgevalue;/边值数组边值数组 int MaxSize,n;/最大边数最大边数,当前边数当前边数;void Graph:Kruskal(MinSpanTree&T)MSTEdgeNode e;/边结点辅助单元边结点辅助单元 MinHeap H(CurrentEdges);int NumVertices=Ve
3、rticesList.last;/顶点个数顶点个数 UFSets F(NumVertices);/并查集并查集F 并初始化并初始化 for(int u=0;u NumVertices;u+)/邻接矩阵邻接矩阵 for(int v=u+1;v NumVertices;v+)if(Edgeuv!=MAXNUM)/所有边所有边 e.tail=u;e.head=v;e.cost=Edgeuv;H.Insert(e);/插入堆插入堆 int count=1;/最小生成树加入边数的计数最小生成树加入边数的计数 while(count NumVertices)H.RemoveMin(e);/从堆中退出一条边
4、从堆中退出一条边 u=F.Find(e.tail);/检测两端点的根检测两端点的根v=F.Find(e.head);if(u!=v)/根不同不在同一连通分量根不同不在同一连通分量 F.Union(u,v);/合并合并 T.Insert(e);/该边存入最小生成树该边存入最小生成树 T count+;(0,5,10)选中选中 (2,3,12)选中选中(1,6,14)选中选中 (1,2,16)选中选中 (3,6,18)舍弃舍弃(3,4,22)选中选中 (4,6,24)舍弃舍弃 (4,5,25)选中选中并查集邻接矩阵表示-2-2-2-2-1-1-1-1-1-1-1-1-1-1-1-102-1-1-1
5、0-2200000 1 2 3 4 5 6-21-11-2-1-421-2-51211-711211F 0 1 2 3 4 5 6 0 28 10 028 0 16 14 1 16 0 12 2 12 0 22 18 3 22 0 25 24 410 25 0 5 14 18 24 0 6继续重复得继续重复得：顶点顶点5加入生成树顶点集合：加入生成树顶点集合：v=5v=4(0,5,10),(5,4,25),(4,3,22),(3,2,12),(2,1,16),(1,6,14)void Graph:Prim(MinSpanTree&T)int NumVertices=VerticesList.l
6、ast;/图顶点数图顶点数 float*lowcost=new floatNumVertices;int*nearvex=new intNumVertices;for(int i=1;i NumVertices;i+)lowcosti=Edge0i;/顶点顶点0到各边的代价到各边的代价 nearvexi=0;/及最短带权路径及最短带权路径 nearvex0=-1;/顶点顶点0加到生成树顶点集合加到生成树顶点集合 MSTEdgeNode e;/最小生成树结点辅助单元最小生成树结点辅助单元 for(i=1;i NumVertices;i+)/循环循环n-1次次,加入加入n-1条边条边 float
7、min=MAXNUM;int v=0;for(int j=0;j NumVertices;j+)if(nearvexj!=-1&lowcostj min)v=j;min=lowcostj;/求生成树外顶点到生成树内顶点具有最小求生成树外顶点到生成树内顶点具有最小 /权值的边权值的边,v是是当前具最小权值的边的位置当前具最小权值的边的位置 if(v)/v=0表示再也找不到要求顶点了表示再也找不到要求顶点了 e.tail=nearvexv;e.head=v;e.cost=lowcostv;T.Insert(e);/选出的边加入生成树选出的边加入生成树 nearvexv=-1;/作该边已加入生成树标记作该边已加入生成树标记 for(j=1;j NumVertices;j+)if(nearvexj!=-1&/j 不在生成树中不在生成树中 Edgevj lowcostj)/需要修改需要修改 lowcostj=Edgevj;nearvexj=v;
最小生成树ppt课件
