最小生成树报告

1、 题目：最小生成树一 存储结构 /1.头文件#include <stdio.h> #include <stdlib.h> #include "time.h"/2.本地数据类型定义 #define MAX 435 /30*29/2=435/3.带权边的定义/* 定义边(x,y)，权为 w */ typedef struct int x, y; int w; edge; /4.本地数组和数据定义 edge eMAX; int tagMAX; /标志 int fatherMAX; /定义 x 的父节点二 基本操作int cmp(const void *a,

2、 const void *b);操作功能: 比较函数，按权值(相同则按 x 坐标)非降序排序 void Make_Set(int x);操作功能：初始化集合int Find_Set(int x);操作功能：查找 x 元素所在的集合,回溯时压缩路径void Union(int x, int y, int w);操作功能：合并 x,y 所在的集合void Select();操作功能：初始化界面三 算法设计/ 1.比较函数，按权值(相同则按 x 坐标)非降序排序 int cmp(const void *a, const void *b) if (*(edge *)a).w = (*(edge *)b

3、).w) return (*(edge *)a).x - (*(edge *)b).x; return (*(edge *)a).w - (*(edge *)b).w; /2. 初始化集合 void Make_Set(int x) fatherx = x; tagx = 0; /3. 查找 x 元素所在的集合,回溯时压缩路径 int Find_Set(int x) while(fatherx) x=fatherx; return x; /4. 合并 x,y 所在的集合 void Union(int x, int y, int w) if (x = y) return; /* 将标志较小的树连接

4、到标志较大的树后 */ if (tagx > tagy) fathery = x; else if (tagx = tagy) tagy+; fatherx = y; /5.初始化界面void Select() printf("n*nn"); printf("Welcome to here!please selected:n");printf(" 最小生成树 n"); printf(" 1. 随机生成权值n"); printf(" 2. 人为输入权值n"); printf(" 3

5、.退出n"); printf("n*nn");6. /堆的实现int heapMAX_N,sz=0;void push(int x)/自己节点的编号int i=sz+;while(i>0) /父亲节点的编号int p=(i-1)/2;/如果已经没有大小颠倒则退出if(heapp<=x)break;/把父亲节点的数值放下来，而把自己提上去heapi=heapp;i=p;heapi=x;int pop()int ret=heap0; /最小值int x=heap-sz;/要提到根的数值int i=0 ; /从根开始往下交集while(i*2+1<sz

6、)/比较儿子的值int a=i*2+1,b=i*2+2;if(b<sz&&heapb<heapa)a=b;/如果已经没有大小颠倒则退出if(heapa>=x)break;heapi=heapa; /把儿子的数值提上来i=a;heapi=x;return ret;四 测试函数main(在里面提供自己输入函数随机生成的图 的选择)int main() int i, numedge=0,choose=0; int x, y; int numnode=0; char chx, chy; Select(); if(scanf("%d",&ch

7、oose)=1) switch(choose) case 1: /随机生成 getchar(); printf("请输入顶点数（<=30）:n"); if(scanf("%d", &numnode)=1) if(numnode>0&&numnode<=30)getchar(); /srand( (unsigned)time( NULL ) ); numedge=(numnode-1)*numnode/2;chx=49;chy=50; for( i = 0; i < numedge;i+ ) ei.w=ran

8、d()%100+1;ei.x = chx - 'A'if(chy=numnode+48)chx+; ei.y = (chy+) - 'A'if(chy=numnode+49) chy=chx+1;Make_Set(i); /forprintf("随机生成的各条边及权值为：n"); for (i = 0; i < numedge; i+) printf("%c - %c : %dn", ei.x + 'A', ei.y + 'A', ei.w);/for/ifelse printf(&q

9、uot;n你的输入范围不对!n"); return 0; /if else printf("!your input is not a number!n"); return 0; break; case 2:/用户自己输入，记得30顶点的无限边最多：30*29/2=435 /边数 getchar();printf("请输入边的条数（不大于 435）:n"); if(scanf("%d", &numedge)=1) if(numedge>0&&numedge<=435) getchar();/

10、清除缓冲区，anyview不允许用fflush() /读取边信息并初始化集合 printf("请输入边的信息（起点，终点，权值(小于100)）分别用空格隔开:n");for (i = 0; i<numedge; i+) scanf("%c %c %d", &chx, &chy, &ei.w);getchar(); ei.x = chx - 'A' ei.y = chy - 'A'Make_Set(i);/for /if elseprintf("您的输入范围有误!n");re

11、turn 0; /ifelseprintf("nYour input is not a number!n");return 0;/else break; case 3: getchar(); printf("your input is error!"); return 0; default: getchar(); printf("nyour choose is false!n"); break; /switch /* 将边排序 */ qsort(e, numedge, sizeof(edge), cmp);printf("最

12、小生成树的各条边及权值为：n");for (i = 0; i < numedge; i+)x = Find_Set(ei.x); y = Find_Set(ei.y); if (x != y ) printf("%c - %c : %dn", ei.x + 'A', ei.y + 'A', ei.w); Union(x, y, ei.w);/for /ifelse printf("your input is not a number!n");return 0; 五 运行结果1.开始界面:提供选择2.输入1：随机生成权值 (2)非法值处理3.输入2，自己构建(2)非法处理3.退出和其他处理六，小结与思考1. 完成情况：（1）1）利用克鲁斯卡尔算法求网的最小生成树。（2）实现并查集。以此表示构造生成树过程中的连通分量。 （3）以文本形式输出生成树中各条边以及他们的权值。（4）堆还没有完成好，只写了几部分操作。2.思考：（1）在设计算法时，需注意判断有关参数的合法性。（2）设计主函数时，需考虑测试的完备性。（3）基础一定要扎实，耐心一定要好，要自主调试程序（4）设置分步检