最小生成树问题中北大学数据结构课程设计

中北大学数据结构与算法课程设计说 明 书学 院 、 系 ： 软件学院专 业 ： 软件工程班 级 ：学 生 姓 名：学 号：设 计 题 目 ： 最小生成树问题起 迄 日 期 : 2015 年 1 月 12 日- 2015 年 1 月 29 日指 导 教 师 : 王秀娟12015 年 1 月 29 日1 需求分析1.1 已知一个无向连通网表示 n 个城市以及城市间可能设置的通信网络线路，其中网的顶点表示城市，边表示两个城市之间的线路，赋于边上的权值表示相应的代价。对于 n 个点的连通网能建立许多不同的生成树，每一棵生成树都可以是一个通信网。我们要选择一棵生成树，使总的耗费最小。1.2 该无向连通图的建立需要使用两种存储结构，即邻接表和邻接矩阵。1.3 实现最小生成树需要使用两种算法。即普里姆算法和克鲁斯卡尔。1.4 程序通过人机交互实现数据的输入和输出。2 选题要求设计内容：在 n 个城市之间建设网络，只需保证连通即可，求最经济的架设方法。存储结构采用（邻接表和邻接矩阵）两种，采用课本上的两种求解算法。设计要求：(1) 符合课题要求，实现相应功能；(2) 要求界面友好美观，操作方便易行；(3) 注意程序的实用性、安全性。3 程序设计方法及主要函数介绍ADT Graph数据对象 V;V 是具有相同特性的数据元素的集合，成为顶点集。数据关系 R：R = VRVR = （v,w）|v,w 为 V 集合中的元素， （v,w）表示 v 和 w 之间存在的路径基本操作 P;CreateMGraph(MGraph *G)2初始条件：V 是图的顶点集，VR 是图的边的集合。操作结果：按 V 和 VR 的定义构造图 G，用邻接矩阵存储。CreateALGraph(ALGraph *G)初始条件：V 是图的顶点集，VR 是图的边的集合。操作结果：按 V 和 VR 的定义构造图 G，用邻接表存储。LocateVex（G，u）初始条件：图 G 存在，u 和 G 中顶点有相同的特征。操作结果：若 G 中存在顶点 u，则返回该顶点在图中的位置；否则返回其他信息。MiniSpanTree_PRIM（G, u)初始条件：图 G 存在，u 是图 G 中的一个顶点。操作结果：用普利姆算法从第 u 个顶点出发构造网 G 的最小生成树 T，输出 T 的各条边。Kriuskal(G)初始条件：图 G 存在操作结果：用克鲁斯卡尔算法构造图 G 的最小生成树 T，输出 T 的各条边。ListToMat(MGraph *G1,ALGraph *G2)初始条件：图 G2 存在操作结果：把图的邻接表存储结构转换为邻接矩阵存储结构，用图 G1 表示。MatToList(MGraph *G1,ALGraph *G2)初始条件：图 G1 存在操作结果：把图的邻接矩阵存储结构转换为邻接表存储结构，用图 G2 表示。LocateVex(MGraph *G,VertexType u)初始条件：图G存在，u和G中顶点有相同特征操作结果：若G中存在顶点u，则返回该顶点在图中位置；否则返回-1ADT Graph4 程序源代码（包括注释）#include #include #include #define OK 13#define ERROR 0#define TURE 1#define FALSE 0#define OVERFLOW -1#define INFEASIBLE -2typedef int Status;#define INFINITY 0#define MAX_VERTEX_NUM 20#define MAX_NAME 5typedef char VertexTypeMAX_NAME;typedef int VRType;typedef struct ArcCell VRType adj;/*顶点关系类型。对无权图，用 1（是）或 0(否）表示相邻否*/*对带权全图，则为权值类型*/ArcCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef struct MGraph VertexType vexsMAX_VERTEX_NUM;/*顶点向量*/AdjMatrix arcs;/*邻接矩阵*/int vexnum,arcnum;/*图的当前顶点数和弧数*/MGraph;/* 以下定义邻接表类型 */typedef struct ANode /* 弧的结点结构类型 */ int end;int begin; /* 该弧的终点位置 */4int weight; /* 该弧的相关信息,这里用于存放权值 */struct ANode *nextarc; /* 指向下一条弧的指针 */ANode;typedef struct VNode /* 邻接表头结点的类型 */ VertexType vertex; /* 顶点信息 */int bianhao;ANode *firstarc; /* 指向第一条弧 */VNode,AdjListMAX_VERTEX_NUM; /* AdjList 是邻接表类型 */typedef struct ALGraph AdjList adjlist; /* 邻接表 */int vexnum,arcnum; /* 图中顶点数 n 和边数 e */ALGraph; /* 图的邻接表类型 */int LocateVex(MGraph *G,VertexType u) /*初始条件：图 G 存在，u 和 G 中顶点有相同特征*/*操作结果：若 G 中存在顶点 u，则返回该顶点在图中位置；否则返回-1*/int i;for(i=0;ivexnum;+i)if(strcmp(u,G-vexsi)=0)return i;return -1;5图一/* 建立无向图的邻接表算法 */Status InitALGraph(ALGraph *G)int i ;printf(“请输入城市的数量及城市间的路径数目n“);scanf(“%d%d“,for(i=0;ivexnum;i+)/* 建立顶点表 */printf(“请输入第%d 个城市的名称n“,i);scanf(“%s“, /* 读入顶点信息 */G-adjlisti.firstarc=NULL;/* 边表置为空表 */G-adjlisti.bianhao = i;printf(“每个城市所对应的序号为n“);for(i = 0;ivexnum;i+)printf(“序号：%d-城市：%sn“,G-adjlisti.bianhao, /注意此处的6Status PrintALGraph(ALGraph *G)int i,end,begin,weight;ANode *s;for(i=0;ivexnum;i+)/* 建立顶点表 */printf(“%s -“,s = G-adjlisti.firstarc;while(s!=NULL)printf(“( %s,%s ):%d “,s = s-nextarc;printf(“n“);return OK;void CreateALGraph(ALGraph *G)int i,j,k,weight;ANode *s;InitALGraph(G);for(k=0;k arcnum;k+) /* 建立边表 */printf(“n 请输入第%d 条边的两个城市的编号及路径的架设费用:“,k);scanf(“%d“,scanf(“%d“,scanf( “%d“,/* 读入边(vi，vj)的顶点对序号 */s=(ANode*)malloc(sizeof(ANode); /* 生成边表结点 */7if(!s) printf(“申请空间失败!n“);exit(OVERFLOW);s-begin=j; /* 邻接点序号为 j */s-end = i;s-weight = weight;s-nextarc= G-adjlisti.firstarc; G-adjlisti.firstarc=s; /*将新结点*s 插入顶点 vi 的边表头部 */s=(ANode*)malloc(sizeof(ANode);if(!s) printf(“申请空间失败!n“);exit(OVERFLOW);s-begin=i; /* 邻接点序号为 i */s-end=j;s-weight=weight;s-nextarc=G-adjlistj.firstarc;G-adjlistj.firstarc=s; /* 将新结点*s 插入顶点 vj 的边表头部 */PrintALGraph(G);/* CreateALGraph */Status PrintMGraph(MGraph *G)int a;int i,j;printf(“邻接矩阵表示法为：n“); printf(“t“);for(i=0;ivexnum;+i) 8printf(“t%5s “,printf(“n“);for ( i=0; ivexnum; i+)printf(“t%5s “,for ( j=0; jvexnum; j+)printf(“t%5d “,G-arcsij.adj);printf(“n“);return OK;图二Status InitMGraph(MGraph *G)int i,j;printf(“请输入城市的数量及城市间的路径数目：n“);scanf(“%d%d“,printf(“n 请依次输入城市的名称，字符串类型n“);9for(i=0;ivexnum;+i)/*构造顶点向量*/scanf(“%s“,for(i=0;ivexnum;+i)/*初始化邻接矩阵*/for(j=0;jvexnum;+j)G-arcsij.adj=INFINITY;return OK;Status CreateMGraph(MGraph *G)/*采用数组（邻接矩阵）表示法，构造无向网 G*/int i,j,k,weight,IncInfo;VertexType va,vb;InitMGraph(G);for(k=0;karcnum;+k) printf(“请输入第%