最小生成树.doc

《数据结构课程设计》姓名: 刘欢学号: 201001051118 班级: 信管 10-1 班成绩: 信息科学与工程学院 2012年6月22日最小生成树的克鲁斯克尔算法的实现一、需求分析若要在 n个城市之间建设通信网络,只需要架设 n-1 条线路即可。如何以最低的经济代价建设这个通信网,是一个最小生成树的问题。本课程设计就是为了解决这个问题的。二、概要设计 ADT { 数据对象: D= { ia | ia? int,i =1,2,3...n,n ? 0} 数据关系: R={< 1?ia , ia >| 1?ia , ia? D, 1?ia < ia ,i=2...n} 基本操作: void (MGraph &G) ; 操作结果:创建图 G 基本操作: int LocateVex(MGraph G,char *v) ; 操作结果:定位和 v匹配的节点,如果有返回其位置,否则返回 0 基本操作: void select(MGraph G,int &v1,int &v2) ; 操作结果:找到 v1,v2 之间的路径最小值基本操作: void keluskar(MGraph G); 操作结果:克鲁斯克尔算法求最小生成树} Int main(){ (G);// 创建一个图; keluskar(G);// 克鲁斯克尔算法生成最小生成树; } 三、详细设计 、节点类型、指针类型 typedef struct ell{ float adj;// 无权图为 1或 0,有权图为权重 char info[30];// 该弧相关信息}ell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; typedef struct { char vexs[MAX_VERTEX_NUM][20];// 顶点向量,如 v1,v2,... 等 int vexs_tap[MAX_VERTEX_NUM];// 新加入的标志元素 AdjMatrix arcs; int vexnum,um; }MGraph; int LocateVex(MGraph G,char *v){ int i,num=-1; for(i=0;i<;i++){ if(strcmp(v,[i])==0) {//相等时为 0,大于为正,小于为负 num=i;break; }} if(num<0){ cout<<" 没有匹配的顶点,输入错误!"<<endl; return -1; } Else return num; } void (MGraph &G){ int i,j,k,s=0; int IncInfo=-1;//IncInfo 为 0则各弧不含其它信息,有信息则为其他数字 char v[2][20];// 存放一条边的两个顶点 char *p; float w;// 输入的权重 int direct=-1;// 有向图为 1,无向图为其他数字//char temp[100][20];// 这个 temp 不能放到本函数内,or,[i] 引用他时,赋了值,//scanf(&,&,&IncInfo); cout<<" 构建有向图请输入数