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

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

专业：_________班级：_________姓名：_________学号：_________完成日期：_________

【问题描述】

给定一个地区的n个城市间的距离网，用Prim算法或Kruskal算法建立最小生成树，并计

算得到的最小生成树的代价。

【设计需求及分析】

1、城市间的距离网采用邻接矩阵表示，邻接矩阵的存储结构定义采用课本中给出的定

义，

若两个城市之间不存在道路，则将相应边的权值设为自己定义的无穷大值。

2、要求在屏幕上显示得到的最小生成树中包括了哪些城市间的道路，并显示得到的最

小生成树的代价。 3、表示城市间距离网的邻接矩阵（要求至少6 个城市，10 条边）。 【设计功能的实现】（用C 或C++语言描述）

#include<iostream.h>

#include<stdio.h>

#include<string.h>

#include<windows.h>

#include"TypeDefine.h"

#include"AdjacencyMatrix.h"

#include"InitializeFunction.h"

#include"MiniSpanTree_KRUSKAL.h"

#include"MiniSpanTree_PRIM.h"

#include"DisplayNet.h"

#include"DeleteInfo.h"

MGraph G;

//全局变量G

intmain(int argc, char * argv[]);//主函数
StatusLocateVex(MGraph G, VertexType v);//判断城市v在网G中的位置StatusCreateUDN(MGraph &G);//创建网G的邻接矩阵
voidDisplayNet(MGraph G);//以邻接矩阵的形式显示网G
voidMiniSpanTree_KRUSKAL(MGraph G);//最小生成树的Kruskal算法voidMiniSpanTree_PRIM(MGraph G, VertexType u);//最小生成树的Prim算法StatusMinimum(closedge closeEdge, int n);//Prim 算法中求下一个城市的函数voidDeleteInfo(MGraph &G);//释放堆内存上动态申请的空间

intmain(int argc, char * argv[])
{
CreateGraph(G);
DisplayNet(G);
MiniSpanTree_KRUSKAL(G);
MiniSpanTree_PRIM(G,G.vexs[0]);
DeleteInfo(G);
cout<<endl<<endl;
system("pause");
return0;
}

//intializeFunction.h

StatusCreateDG(MGraph &G){return 0;};
StatusCreateDN(MGraph &G){return 0;};
StatusCreateUDG(MGraph &G){return 0;};
StatusCreateUDN(MGraph &G);

StatusLocateVex(MGraph G, VertexType v)

{
//判断输入的顶点v在G中的位置。

//根据顶点的类型，可重载此函数。目前为char
inti=0;
while(strcmp(G.vexs[i], v)) {i++;}
returni;
}

StatusCreateGraph(MGraph &G)
{
//采用数组（邻接矩阵）表示法，构造图G.

G.kind= UDN; //默认构造无向网
/* printf("+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n");
printf("|1:有向图2:无向图3:有向网4:无向网\n");
printf("|请选择:[]\b\b");
scanf("%d",&G.kind);
printf("+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n");*/

switch(G.kind)
{
case DG: return CreateDG(G); //构造有向图G
case DN: return CreateDN(G); //构造有向网G
caseUDG: return CreateUDG(G); //构造无向图G
caseUDN: return CreateUDN(G); //构造无向网G
default: return ERROR;
}
}//CreateGraph

StatusCreateUDN(MGraph &G)
{

//采用数组（邻接矩阵）表示法，构造图G.

inti, j, k;
VertexTypev1, v2;
VRTypew;
printf(" 构造可以使N个城市连接的最小生成树\n");printf("请输入城市数、道路数(至少6个城市，10条道路)：");
cin>>G.vexnum>>G.arcnum;

for(i=0; i<G.vexnum; ++i) //构造顶点向量
{
printf("请输入第%d个城市名（共%d个）:",i+1, G.vexnum); cin>>G.vexs[i];
}

for(i=0; i<G.vexnum; ++i) //初始化邻接矩阵
{
for(j=0; j<G.vexnum; ++j)
{
G.arcs[i][j].adj= INFINITY;
// G.arcs[i][j].info= NULL;
}
}

printf("请输入一条道路连接的两个城市名及权值:\n");
for(k=0; k<G.arcnum; ++k) //构造邻接矩阵
{
printf("共%3d条道路，第%3d条道路：",G.arcnum,k+1);

cin>>v1>>v2>>w; i = LocateVex(G, v1);

//输入一条边依附的顶点及权值//确定v1、v2 在G 中的位置

j= LocateVex(G, v2);

G.arcs[i][j].adj = w; G.arcs[j][i] = G.arcs[i][j];

//弧<v1,v2>的权值 //置<v1,v2>的对称弧<v2,v1>

}

returnOK;
}//CreateUDN

//MiniSpanTree PRIM.h

StatusMinimum(closedge closeEdge, int n)
{
inti, flag, minTemp = INFINITY;
for(i=0; i<n; ++i)
{
if((closeEdge[i].lowcost != 0) && (minTemp >closeEdge[i].lowcost)) {
minTemp= closeEdge[i].lowcost;
flag= i;
}
}
returnflag;
}

voidMiniSpanTree_PRIM(MGraph G, VertexType u)
{
//用普里姆算法从第u个顶点出发构造网G的最小生成树T，输出T的各条边。 //记录从顶点集U到V-U的代价最小的边的辅助数组定义见"AdjacencyMatrix.h"

inti, j, k, totalCost=0;
closedgecloseEdge;
k= LocateVex(G, u);
for(j=0; j<G.vexnum; ++j) //辅助数组初始化
{
if(j != k)
{
strcpy(closeEdge[j].adjvex,u);
closeEdge[j].lowcost= G.arcs[k][j].adj;
}
}

cout<<"\n\n+^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^\\\n";
cout<<"|用Prim算法求最小生成树的各条边依次为：\n-----";
closeEdge[k].lowcost= 0; //初始，U={u};
for(i=1; i<G.vexnum; ++i) //选择其余G.vexnum-1个顶点
{
k= Minimum(closeEdge, G.vexnum);
//求出T的下一个结点：第k顶点 //此时closeEdge[k].lowcost= MIN{closeEdge[vi].lowcost | closeEdge[vi].lowcost > 0, vi∈V-U}
cout<<'<'<<closeEdge[k].adjvex<<','<<G.vexs[k]<<'>'; //输出生成树的边
totalCost+= closeEdge[k].lowcost;
closeEdge[k].lowcost= 0; //第k顶点并入U集

for(j=0; j<G.vexnum; ++j)
{
if(G.arcs[k][j].adj < closeEdge[j].lowcost) //新顶点并入U后重新选择最小边 {
strcpy(closeEdge[j].adjvex,G.vexs[k]);
closeEdge[j].lowcost= G.arcs[k][j].adj;

}
}
}
cout<<"\n|总代价："<<totalCost<<endl;
cout<<"+^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^/\n";
}//MiniSpanTree

【实例测试及运行结果】

【使用说明】
心得体会：
【选作内容】