《程序设计》课程设计
姓 名：王 学 号：20100034 班 级：软件工程00班 指导教师： 王会青 成 绩：
2010年6月
- 1 -
实验一.构造可以使n个城市连接的最小生成树
专业：__软件工程___ 班级：__软件 姓名：_王___ 学号：_20100034 完成日期：_2010/6/26________
一、【问题描述】
给定一个地区的n个城市间的距离网，用Prim算法或Kruskal算法建立最小生成树，并计算得到的最小生成树的代价。
1 城市间的道路网采用邻接矩阵表示，邻接矩阵的存储结构定义采用课本中给出的定义，若两个城市之间不存在道路，则将相应边的权值设为自己定义的无穷大值。 2 显示出城市间道路网的邻接矩阵。
3 最小生成树中包括的边及其权值，并显示得到的最小生成树的总代价。
4 输入城市数、道路数→输入城市名→输入道路信息→执行Kruskal 算法→执行 Prim 算法→输出最小生成树
二、【问题分析】
1.抽象数据类型结构体数组的定义：
#ifndef ADJACENCYMATRIXED //防止该头文件被重复引用
#define ADJACENCYMATRIXED
//而引起的数据重复定义
#define INFINITY 32767 //最大值∞
#define MAX_VERTEX_NUM 20 //最大顶点个数
typedef int VRType; //权值，即边的值 typedef char InfoType; //附加信息的类型，后面使用时会定义成一个指针 typedef char VertexType[MAX_VERTEX_NUM]; //顶点类型
typedef enum {DG=1, DN, UDG, UDN} GraphKind; //{有向图，有向网，无向图，无向网}
typedef struct ArcCell { VRType adj; //VRType 是顶点关系类型。对无权图，用 1 或 0 表示相邻否；对带权图，则为权值类型。 InfoType*info; //该弧关系信息的指针
}ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
- 2 -
typedef struct { VertexType vexs[MAX_VERTEX_NUM]; //顶点向量 AdjMatrix arcs; //邻接矩阵 int vexnum, arcnum; //图的当前顶点数和弧数 GraphKind kind; //图的种类标志 }MGraph;
typedef struct //普里姆算法辅助数组的定义 { VertexType adjvex; VRType lowcost; }closedge[MAX_VERTEX_NUM];
#endif //结束if
2 程序模块
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); //释放堆内存上动态申请的空间
3.流程图
创建用邻接矩阵表示的城市道路网 输入城市数G.vexnum、 道路数G.arcnum 输入城市名G.vexs[i] - 3 -
输入表示道路的两个城市及道路值G.arcs[i][j].adj 返回 OK
Prim算法 化辅助数组closeEdge for (i=1; i 4.数据类型定义 为了用邻接矩阵表示图 G ，先是定义二维数组的每一个元素含道路值然后在图的定义中定义一个此二维数组的结构成员。并且在图中还定义一个用来存放城市的一维数组及int 型的城市数级道路数。 用二维数组的两个下标表示道路，这两个下标又在一位数组中对应两个城市。 这样就建立起了一个城市到城市之间的道路网。 - 4 - 4. 程序主要模块 说明：该程序共含5个模块，本人负责其中2个模块构造： ***************LocateVex(MGraph G, VertexType v)**************** Status LocateVex(MGraph G, VertexType v); { } **************** CreateUDN************************* { } PRIM算法 ************************** MiniSpanTree_PRIM********* void MiniSpanTree_PRIM(MGraph G, VertexType u) { 定义辅助数组：closedge closeEdge; 初始化：strcpy(closeEdge[j].adjvex, u); closeEdge[j].lowcost = G.arcs[k][j].adj; - 5 - while (strcmp(G.vexs[i], v)) {i++;} 返回 i； 输入城市数、道路数； for (i=0; i<城市数; ++i) 输入城市名； for (i=0; i<城市数; ++i) for(j=0; j<城市数; ++j) 初始化邻接矩阵：道路值= INFINITY; for (i=0; i<城市数; ++i) for(j=0; j<城市数; ++j) 输入两个城市表示道路，输入道路值；