构造可以使N个城市连接的最小生成树
专业:_________ 班级:_________ 姓名:_________ 学号:_________ 完成日期:_________
【问题描述】
给定一个地区的n个城市间的距离网,用Prim算法或Kruskal算法建立最小生成树,并计算得到的最小生成树的代价。
【设计需求及分析】
1、城市间的距离网采用邻接矩阵表示,邻接矩阵的存储结构定义采用课本中给出的定义,
若两个城市之间不存在道路,则将相应边的权值设为自己定义的无穷大值。
2、要求在屏幕上显示得到的最小生成树中包括了哪些城市间的道路,并显示得到的最小生成树的代价。
3、表示城市间距离网的邻接矩阵(要求至少6个城市,10条边)。
【设计功能的实现】(用C或C++语言描述)
#include <>
#include <>
#include <>
#include <>
#include ""
#include ""
#include ""
#include ""
#include ""
#include ".h"
#include ""
MGraph G; //全局变量G
int main(int argc, char * argv[]);//主函数
Status LocateVex(MGraph G, VertexType v);//判断城市 v 在网 G 中的位置
Status CreateUDN(MGraph &G);//创建网 G 的邻接矩阵
void (MGraph G);//以邻接矩阵的形式显示网 G
void MiniSpanTree_KRUSKAL(MGraph G);//最小生成树的 Kruskal 算法
void MiniSpanTree_PRIM(MGraph G, VertexType u);//最小生成树的 Prim 算法
Status Minimum(closedge closeEdge, int n);//Prim 算法中求下一个城市的函数
void DeleteInfo(MGraph &G);//释放堆内存上动态申请的空间
int main(int argc, char * argv[])
{
CreateGraph(G);
(G);
MiniSpanTree_KRUSKAL(G);
MiniSpanTree_PRIM(G, [0]);
DeleteInfo(G);
cout<<endl<<endl;
system("pause");
return 0;
}
//
Status CreateDG(MGraph &G){return 0;};
Status CreateDN(MGraph &G){return 0;};
Status CreateUDG(MGraph &G){return 0;};
Status
构造可以使N个城市连接最小生成树 来自淘豆网m.daumloan.com转载请标明出处.