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

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

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

【问题描述】

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

【设计需求及分析】

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

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

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

3、表示城市间距离网的邻接矩阵（要求至少6个城市，10条边）。

【设计功能的实现】（用C或C++语言描述）

#include

#include

#include

#include

#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

int main(int argc, char * argv[]);//主函数

Status LocateVex(MGraph G, VertexType v);//判断城市 v 在网 G 中的位置

Status CreateUDN(MGraph &G);//创建网 G 的邻接矩阵

void DisplayNet(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);

DisplayNet(G);

MiniSpanTree_KRUSKAL(G);

MiniSpanTree_PRIM(G, G.vexs[0]);

DeleteInfo(G);

cout<system(\"pause\");

return 0;

}

//intializeFunction.h

Status 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中的位置。

//根据顶点的类型，可重载此函数。目前为char

int i=0;

while (strcmp(G.vexs[i], v)) {i++;}

return i;

}

Status CreateGraph(MGraph &G)

{

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

G.kind = UDN; //默认构造无向网

/* printf(\"+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\\n\");

printf(\"|1:有向图 2:无向图 3:有向网 4:无向网\\n\");

printf(\"|请选择:[ ]\\b\\b\");

scanf(\"%d\

printf(\"+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\\n\");*/

switch (G.kind)

{

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;

}

}//CreateGraph

Status CreateUDN(MGraph &G)

{

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

int i, j, k;

VertexType v1, v2;

VRType w;

printf(\" 构造可以使N个城市连接的最小生成树\\n\");

printf(\"请输入城市数、道路数(至少6个城市，10条道路)：\");

cin>>G.vexnum>>G.arcnum;

for (i=0; i{

printf(\"请输入第 %d 个城市名（共 %d 个）:\

cin>>G.vexs[i];

}

for (i=0; i{

for (j=0; j{

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

// G.arcs[i][j].info = NULL;

}

}

printf(\"请输入一条道路连接的两个城市名及权值:\\n\");

for (k=0; k{

printf(\"共%3d条道路，第%3d条道路：\

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]; //置的对称弧

}

return OK;

}//CreateUDN

//MiniSpan Tree PRIM.h

Status Minimum(closedge closeEdge, int n)

{

int i, flag, minTemp = INFINITY;

for (i=0; i{

if ((closeEdge[i].lowcost != 0) && (minTemp > closeEdge[i].lowcost))

{

minTemp = closeEdge[i].lowcost;

flag = i;

}

}

return flag;

}

void MiniSpanTree_PRIM(MGraph G, VertexType u)

{

//用普里姆算法从第 u 个顶点出发构造网 G 的最小生成树 T，输出 T 的各条边。

//记录从顶点集 U 到 V-U 的代价最小的边的辅助数组定义见 \"AdjacencyMatrix.h\"

int i, j, k, totalCost=0;

closedge closeEdge;

k = LocateVex(G, u);

for (j=0; 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{

k = Minimum(closeEdge, G.vexnum); //求出 T 的下一个结点：第 k 顶点

//此时 closeEdge[k].lowcost = MIN{closeEdge[vi].lowcost |

closeEdge[vi].lowcost > 0, vi∈V-U}

cout<<'<'<'; //输出生成树的边

totalCost += closeEdge[k].lowcost;

closeEdge[k].lowcost = 0; //第 k 顶点并入 U 集

for (j=0; 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|总代价：\"<cout<<\"+^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^/\\n\";

}//MiniSpanTree

【实例测试及运行结果】

【使用说明】

心得体会：

【选作内容】