数据结构—最小生成树

《数据结构—最小生成树》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、实验：最小生成树-、程序设计简介本验证程序实现了Prim算法。程序提供图的创建和用Prim求最小生成树。图的存储采用了数组存储。运行结果输出创建的图信息及求得的最小生成树。二、源程序(1)Minitree_prim.h/*-最小生成树(图采用数组存储结构举例表示)*///#include"MGraph.h"#include#include〈iostream〉#include〈string〉usingnamespace$td;#ifndefMGRAPH#defineMGRAPH#defineMAX_VERTEX_NUM20//最大顶点

2、数#defineMAXEDGE190//图中的最大边数constintinfinity=INT—MAX;structArcCell{intadj;//对无权图有1，0表示是否相邻，对带权图，则为权值类型char*info;//该弧的相关信息template〈classT>structminisidej//记录从顶点集u到顶点集v-u的代价最小的边的辅助数组定义Tadjvex;intlowcost;templatestructEdgeTpe{Tvl;Tv2;intcost;templatestruct_MGraph{T

3、vexs[MAX一VERTEX一NUM];ArcCellarcslMAX_VERTEX_NUMJlMAX_VERTEX_NUMJ;intvexnum;intarcnum;intkind;templateclassMGraph{_MGraphmgraph;boolvisited[MAX_VERTEX_NUM];public:boolCreateUDN();intMinimum(miniside*SZ);intLocateVex(Tu);图屮的位貫voidDisPlayO;voidMiniSpanTree_PRIM(Tu);小

4、生成树，并输出各条边voidDestroyGraph();};template〈classT>voidMGraph::DisPlayO{inti，j;//输出权值的邻接矩阵cout«"无向网的邻接矩阵为"<

5、=infinity)cout«setw(l5)«"°°elsecout«setw(15)«mgraph.arcs[i][j].adj«,t,;}cout«endl«endl:template〈classT>boolMGraph::CreateUDNO//构造无向网inti，j，w;Tvl，v2;COut«n请输入无向网的顶点个数，边的个数:"；cin»mgraph.vexnum〉〉mgraph.arcnuni;cout«"请输入各个顶点:";for(i=O;i

6、s[ij;)for(i=O;i

7、>mgraph.arcs[n][m].adj=w;//)mgraph.kind=3;returntrue;}template〈classT>voidMGrapharcs[i][j].info)delete[]mgraph.arcs[i][j].info;mgraph.arcs[i][j]-info=mgraph.arcs

8、j][ij.info=

9、false;)}mgraph.vexnum=0;mgraph.arcnum=0;)template