《构造可以使N个城市连接的最小生成树》由会员分享，可在线阅读，更多相关《构造可以使N个城市连接的最小生成树（7页珍藏版）》请在装配图网上搜索。
1、构造可以使N个城市连接的最小生成树专业：班级：姓名：学号：完成日期：【问题描述】并计给定一个地区的n个城市间的距离网， 用Prim算法或Kruskal算法建立最小生成树, 算得到的最小生成树的代价。【设计需求及分析】1、城市间的距离网采用邻接矩阵表示，邻接矩阵的存储结构定义采用课本中给出的定 义，若两个城市之间不存在道路，则将相应边的权值设为自己定义的无穷大值。2、要求在屏幕上显示得到的最小生成树中包括了哪些城市间的道路，并显示得到的最 小生成树的代价。3、 表示城市间距离网的邻接矩阵（要求至少6个城市，10条边）。【设计功能的实现】（用C或C+语言描述）#in elude #i nclude
2、 #in clude #in clude #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.hMGraph G;全局变量Gint main(int argc, char * argv); 主函数Status LocateVex(MGraph G, VertexType
3、 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
4、);/释放堆内存上动态申请的空间int main (i nt argc, char * argv)CreateGraph(G);DisplayNet(G);Mi niSpa nTree_KRUSKAL(G);MiniSpanTree_PRIM(G , G.vexs0);DeleteI nfo(G);coute ndlG.vexnumG .arcnum;/构造顶点向量printf（请输入第d个城市名（共%d 个)：，i+1, G .vexnum);for (i=0; i G.vexsi;for (i=0; iG.vex num; +i)/ 初始化邻接矩阵for (j=0; jG .vexnum;
5、 +j)G.arcsij.adj = INFINITY;/ G.arcsij.i nfo = NULL;printf（请输入一条道路连接的两个城市名及权值:n）;for （k=0; kv1v2w;输入一条边依附的顶点及权值i = LocateVex(G, v1);/确定v1、v2在G中的位置j = LocateVex(G, v2);G.arcsij.adj = w;/弧 的权值G.arcsji = G .arcsij;置 的对称弧 return OK;/CreateUDN/MiniSpan Tree PRIM hStatus Minimu m(closedge closeEdge, int n
6、)int i, flag, mi nTemp = INFINITY;for (i=0; i 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.hint i, j, k, totalCost=0;closedge closeEdge;k = LocateV
7、ex(G, u);for (j=0; jG.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 0, vi V-UcoutcloseEdgek.adjvex,G .vexsk;输出生成树的边totalCost += closeEdgek.lowcost;closeEdgek.lowcost = 0;/第 k 顶点并入 U 集for (j=0; jG .vexnum; +j)if (G.arcskj.adj closeEdgej.lowcost)新顶点并入U 后重新选择最小边strcpy(closeEdgej.adjvex, G .vexsk);closeEdgej.lowcost = G .arcskj.adj;coutn| 总代价：totalCostendl;cout+AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA/Mi niSpa nTree【实例测试及运行结果】【使用说明】心得体会：【选作内容】
构造可以使N个城市连接的最小生成树
