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

1、中北大学数据结构与算法课程设计说 明 书学 院、系：软件学院专 业：软件工程班 级：学 生 姓 名：学 号：设 计 题 目：最小生成树问题 起 迄 日 期:2015年1月12日- 2015年1月29日指 导 教 师:王秀娟2015 年1月 29 日1 需求分析1.1已知一个无向连通网表示n个城市以及城市间可能设置的通信网络线路，其中网的顶点表示城市，边表示两个城市之间的线路，赋于边上的权值表示相应的代价。对于n个点的连通网能建立许多不同的生成树，每一棵生成树都可以是一个通信网。我们要选择一棵生成树，使总的耗费最小。1.2该无向连通图的建立需要使用两种存储结构，即邻接表和邻接矩阵。1.3实现最小

2、生成树需要使用两种算法。即普里姆算法和克鲁斯卡尔。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;CreateMGr

3、aph(MGraph *G)初始条件：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

4、(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程序源代码

5、（包括注释）#include #include #include #define OK 1#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; /*顶点关

6、系类型。对无权图，用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; /* 该弧的终点位置

7、 */ int 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

8、,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;图一/* 建立无向图的邻接表算法 */Status InitALGraph(ALGraph *G) int i ; printf(请输入城市的数量及城市间的路径数

9、目n); scanf(%d%d,&G-vexnum,&G-arcnum); for(i=0;ivexnum;i+) /* 建立顶点表 */ printf(请输入第%d个城市的名称n,i); scanf(%s,&G-adjlisti.vertex); /* 读入顶点信息 */ G-adjlisti.firstarc=NULL;/* 边表置为空表 */ G-adjlisti.bianhao = i; printf(每个城市所对应的序号为n); for(i = 0;ivexnum;i+) printf(序号：%d-城市：%sn,G-adjlisti.bianhao,&G-adjlisti.verte

10、x); /注意此处的& return OK;Status PrintALGraph(ALGraph *G) int i,end,begin,weight; ANode *s; for(i=0;ivexnum;i+)/* 建立顶点表 */ printf(%s -,&G-adjlisti.vertex); s = G-adjlisti.firstarc; while(s!=NULL) printf( %s,%s ):%d ,&G-adjlists-end.vertex,&G-adjlists-begin.vertex,s-weight); s = s-nextarc; printf(n); ret

11、urn 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,&i); scanf(%d,&j); scanf( %d,&weight);/* 读入边(vi，vj)的顶点对序号 */ s=(ANode*)malloc(sizeof(ANode); /* 生成边表结点 */ if(!s) printf(申请空间失败!n); exit(OVE

12、RFLOW); 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-ad

13、jlistj.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) printf(t%5s ,&G-vexsi); printf(n); for ( i=0; ivexnum; i+) printf(t%5s ,&G-vexsi); for ( j=0; jvexnum; j+) printf(t%5d ,G-arc

14、sij.adj); printf(n); return OK;图二Status InitMGraph(MGraph *G) int i,j; printf(请输入城市的数量及城市间的路径数目：n); scanf(%d%d,&G-vexnum,&G-arcnum); printf(n请依次输入城市的名称，字符串类型n); for(i=0;ivexnum;+i) /*构造顶点向量*/ scanf(%s,&G-vexsi); for(i=0;ivexnum;+i) /*初始化邻接矩阵*/ for(j=0;jvexnum;+j) G-arcsij.adj=INFINITY; return OK;Sta

15、tus CreateMGraph(MGraph *G)/*采用数组（邻接矩阵）表示法，构造无向网G*/ int i,j,k,weight,IncInfo; VertexType va,vb; InitMGraph(G); for(k=0;karcnum;+k) printf(请输入第%d条路径的起点城市和终点城市的名称及路径的架设费用n,k); scanf(%s %s %d,&va,&vb,&weight); i=LocateVex(G,va); j=LocateVex(G,vb); G-arcsij.adj=weight; G-arcsji.adj=weight; PrintMGraph(G

16、); return OK;typedef struct MINSIZE/记录从顶点集U到V-U的代价最小的边的辅助数组定义* VertexType adjvex; VRType lowcost;minsideMAX_VERTEX_NUM;Status mininum(minside closedge,MGraph *G)/*求closedege,lowcost的最小正值*/ int i=0,j,k,min; while(!closedgei.lowcost) i+; min=closedgei.lowcost; k=i; for(j=i+1;jvexnum;j+) if(closedgej.l

17、owcost0) if(minclosedgej.lowcost) min=closedgej.lowcost; k=j; return k;图三void MiniSpanTree_PRIM(MGraph *G,VertexType u)/*用普利姆算法从第u个顶点出发构造网G的最小生成树T，输出T的各条边*/ int i,j,k; int qidian,zhongdian,weight; VertexType va,vb; minside closedge; k=LocateVex(G,u); for(j=0;jvexnum;+j) /*辅助数组初始化*/ if(j!=k) strcpy(c

18、losedgej.adjvex,u); closedgej.lowcost=G-arcskj.adj; closedgek.lowcost=0; /*初始U=u*/ printf(最小代价生成树的各条边为:n); for(i=1;ivexnum;+i) /*选择其余G.vexnum-1个顶点*/ k=mininum(closedge,G); /*求出T的下一个结点：第K顶点*/ strcpy( va,closedgek.adjvex); strcpy(vb ,G-vexsk); qidian=LocateVex(G,va); zhongdian=LocateVex(G,vb); weight

19、= G-arcsqidianzhongdian.adj; printf(weight(%s,%s)=%dn,va,vb,weight); /*输出生成树的边*/ closedgek.lowcost=0; /*第K顶点并入U集*/ for(j=0;jvexnum;+j) if(G-arcskj.adjvexsk); closedgej.lowcost=G-arcskj.adj; void InsertSort(ANode *E,int n) /对E0.n-1按权值递增有序的进行直接插入排序 int i,j; ANode temp; for(i=1;i=0&temp.weightvexnum; E

20、=(struct ANode*)malloc(n*sizeof(struct ANode); k=0; for(i=0;ivexnum;i+) /* 将各边存到E0.n数组中 */ for(j=0;jvexnum;j+) s = G-adjlisti.firstarc; while(s!=NULL) (E+k)-end = s-end; (E+k)-begin = s-begin; (E+k)-weight = s-weight ; s = s-nextarc; k+; InsertSort(E,k); /* 对E数组按w递增排序 */ for(i=0;ivexnum;i+) vseti=i;

21、 /* 初始化辅助数组 */ k=1; j=0; while(kvexnum) /* 生成的边数小于n时循环 */ end=(E+j)-end; begin=(E+j)-begin; /* 取一条边的头尾顶点 */ sn1=vsetend; sn2=vsetbegin;/* 分别得到两个顶点所属的集合编号 */ if(sn1!=sn2) /* 两顶点属不同集合，则该边是最小生成树的一条边 */ printf( weight(%s %s) : %dn,&(G-adjlistend.vertex),&(G-adjlistbegin.vertex),(E+j)-weight); k+; /* 生成边

22、数增1 */ for(i=0;in;i+)/* 两个集合统一编号 */ if(vseti=sn2) vseti=sn1; j+; /* 扫描下一条边 */ 图五Status ListToMat(MGraph *G1,ALGraph *G2) int i,j; ANode *s; for(i = 0;ivexnum;i+) strcpy(G1-vexsi, G2-adjlisti.vertex); for(j = 0;jvexnum;j+) G1-arcsij.adj=INFINITY; for(i = 0;ivexnum;i+) s = G2-adjlisti.firstarc; while(

23、s) G1-arcss-ends-begin.adj = s-weight; s =s-nextarc; G1-vexnum = G2-vexnum; G1-arcnum = G2-arcnum; PrintMGraph(G1); return OK;图六Status MatToList(MGraph *G1,ALGraph *G2) int i,j; ANode *s,*temp; for(i = 0;ivexnum;i+) strcpy(G2-adjlisti.vertex ,G1-vexsi); G2-adjlisti.firstarc = NULL; for(i = 0;ivexnum

24、;i+) for(j = 0;jvexnum;j+) if(G1-arcsij.adj!=INFINITY) s = (struct ANode*)malloc(sizeof(struct ANode); s-end = i; s-begin = j; s-weight = G1-arcsij.adj; s-nextarc=NULL; if(G2-adjlisti.firstarc=NULL) G2-adjlisti.firstarc = s; else s-nextarc = G2-adjlisti.firstarc; G2-adjlisti.firstarc = s; G2-vexnum

25、= G1-vexnum; G2-arcnum = G1-arcnum; PrintALGraph(G2); return OK;Status SelectSaveStructure() int c; printf(请选择一种算法存储无向图n); printf(*n); printf(| 1：邻接矩阵 2：邻接表|n); printf(*n); printf(请按键选择: ); while(1) scanf(%d,&c); if(c=1|c=2) break; else printf(输入的数字不符合要求，请从新输入n); getchar(); return c;Status SelectSua

26、nFa() int c; printf(请选择一种算法构建最小生成树n); printf(*n); printf(| 1：普里姆算法（Prim） 2：克鲁斯卡尔算法（Kruskal）|n); printf(*n); printf(请按键选择: ); while(1) scanf(%d,&c); if(c=1|c=2) break; else printf(输入的数字不符合要求，请从新输入n); getchar(); return c;int main() MGraph *G1; ALGraph *G2; int choose; G2=(ALGraph *)malloc(sizeof(ALGra

27、ph); choose = SelectSaveStructure(); switch(choose) case 1: CreateMGraph(G1); printf(邻接矩阵转换为邻接表mat to listn); MatToList(G1,G2); break; case 2: G2=(ALGraph*)malloc(sizeof(ALGraph); if(!G2) exit(OVERFLOW); CreateALGraph(G2); printf(邻接表转换为邻接矩阵list to matn); ListToMat(G1,G2); break; choose =SelectSuanFa(); switch(