构造可以使N个城市连接的最小生成树

构造可以使N个城市连接的最小生成树专业：班级：姓名：学号：完成日期：【问题描述】并计给定一个地区的n个城市间的距离网， 用Prim算法或Kruskal算法建立最小生成树, 算得到的最小生成树的代价。【设计需求及分析】1、城市间的距离网采用邻接矩阵表示，邻接矩阵的存储结构定义采用课本中给出的定 义，若两个城市之间不存在道路，则将相应边的权值设为自己定义的无穷大值。2、要求在屏幕上显示得到的最小生成树中包括了哪些城市间的道路，并显示得到的最 小生成树的代价。3、 表示城市间距离网的邻接矩阵（要求至少6个城市，10条边）。【设计功能的实现】（用C或C+语言描述）#in elude <iostream.h>#i nclude <stdio.h>#in clude <stri ng.h>#in clude <win dows.h>#i nclude "TypeDefi ne.h"#i nclude "Adjace ncyMatrix.h"#in clude "I nitializeF unction.h"#i nclude "Min iSpa nTree_KRUSKAL.h"#in clude "Mi niSpa nTree_PRIM.h"#include "DisplayNet.h"#i nclude "DeleteI nfo.h"MGraph G;全局变量Gint main(int argc, char * argv); 主函数Status LocateVex(MGraph G, VertexType v); 判断城市 v 在网 G 中的位置Status CreateUDN(MGraph &G); 创建网 G 的邻接矩阵void DisplayNet(MGraph G);以邻接矩阵的形式显示网Gvoid MiniSpanTree_KRUSKAL(MGraph G);最小生成树的Kruskal 算法void MiniSpanTree_PRIM(MGraph G , VertexType u);最小生成树的Prim 算法Status Mi nimum(closedge closeEdge, i nt n);/Prim 算法中求下一个城市的函数 void DeleteInfo(MGraph &G);/释放堆内存上动态申请的空间int main (i nt argc, char * argv)CreateGraph(G);DisplayNet(G);Mi niSpa nTree_KRUSKAL(G);MiniSpanTree_PRIM(G , G.vexs0);DeleteI nfo(G);cout<<e ndl<<e ndl;system("pause");return 0;/intializeFunction hStatus CreateDG(MGraph & G)return 0;Status CreateDN(MGraph & G)return 0;Status CreateUDG(MGraph & G)return 0;Status CreateUDN(MGraph & G);Status LocateVex(MGraph G, VertexType v)判断输入的顶点 v在G中的位置。/根据顶点的类型，可重载此函数。目前为 charint i=0;while (strcmp(G.vexsi, v) i+;return i;Status CreateGraph(MGraph &G) 采用数组（邻接矩阵）表示法，构造图 G.G.ki nd = UDN;默认构造无向网/*prin tf("+*n");printf（"|1:有向图2:无向图 3:有向网 4:无向网n"）;printf("| 请选择:bb");scanf("%d", &G .kind);prin tf("+*n");*/switch (G.ki nd)case DG: return CreateDG(G); 构造有向图 G case DN: return CreateDN(G); 构造有向网 G case UDG: return CreateUDG(G); / 构造无向图 G case UDN: return CreateUDN(G); / 构造无向网 G default : return ERROR;/CreateGraphStatus CreateUDN(MGraph &G)int i, j, k;VertexType v1, v2;VRType w;printf（"构造可以使N个城市连接的最小生成树 n"）;printf（"请输入城市数、道路数（至少6个城市，10条道路）："）;cin>>G.vexnum»G .arcnum;/构造顶点向量printf（"请输入第d个城市名（共%d 个)："，i+1, G .vexnum);for (i=0; i<G.vex num; +i)cin> >G.vexsi;for (i=0; i<G.vex num; +i)/ 初始化邻接矩阵for (j=0; j<G .vexnum; +j)G.arcsij.adj = INFINITY;/ G.arcsij.i nfo = NULL;printf（"请输入一条道路连接的两个城市名及权值:n"）;for （k=0; k<G.arc num; +k）/ 构造邻接矩阵printf（"共%3d 条道路，第 %3d 条道路：", G.arcnum,k+1）;cin >>v1»v2»w;输入一条边依附的顶点及权值i = LocateVex(G, v1);/确定v1、v2在G中的位置j = LocateVex(G, v2);G.arcsij.adj = w;/弧 <v1,v2> 的权值G.arcsji = G .arcsij;置 <v1,v2> 的对称弧 <v2,v1>return OK;/CreateUDN/MiniSpan Tree PRIM hStatus Minimu m(closedge closeEdge, int n)int i, flag, mi nTemp = INFINITY;for (i=0; i<n; +i)if (closeEdgei.lowcost != 0) && (min Temp > closeEdgei.lowcost)mi nTemp = closeEdgei.lowcost;flag = i;return flag;void MiniSpanTree_PRIM(MGraph G , VertexType u)/用普里姆算法从第u个顶点出发构造网G的最小生成树 T,输出T的各条边。/记录从顶点集U至U V-U的代价最小的边的辅助数组定义见"AdjacencyMatrix.h"int i, j, k, totalCost=0;closedge closeEdge;k = LocateVex(G, u);for (j=0; j<G.vex num; +j)/ 辅助数组初始化if (j != k)strcpy(closeEdgej.adjvex, u); closeEdgej.lowcost = G .arcskj.adj;cout<<"|用Prim算法求最小生成树的各条边依次为：n"closeEdgek .lo wcost = 0;/ 初始，U=u;for (i=1; i<G.vex num; +i)/ 选择其余 G.vex nu m-1 个顶点k = Minimum(closeEdge, G.vexnum);/求出 T 的下一个结点：第k 顶点此时 closeEdgek.lowcost = MINcloseEdgevi.lowcost | closeEdgevi.lowcost > 0, vi V-Ucout<<'<'<<closeEdgek.adjvex<<','<<G .vexsk<<'>'输出生成树的边totalCost += closeEdgek.lowcost;closeEdgek.lowcost = 0;/第 k 顶点并入 U 集for (j=0; j<G .vexnum; +j)if (G.arcskj.adj < closeEdgej.lowcost)新顶点并入U 后重新选择最小边strcpy(closeEdgej.adjvex, G .vexsk);closeEdgej.lowcost = G .arcskj.adj;cout<<"n| 总代价："<<totalCost<<endl;cout<<"+AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA/Mi niSpa nTree【实例测试及运行结果】【使用说明】心得体会：【选作内容】