《数据结构》课程设计普里姆算法最小生成树.doc
数据结构课程设计报告蔡金林18031944一设计课题：管道铺设施工的最佳方案选择.N (N>10)个居名之间需要铺设煤气管道.假设任意两个居名之间都可以铺设煤气管道,但代价不同.事先将任意两个居名之间铺设煤气管道的代价存入磁盘文件中.设计一个最佳方案使得这N个居名之间铺设煤气管道所需要代价最少,并希望以图形方式在屏幕上输出结果。二算法思想：要在个城市之间铺设煤气管道，则连通个城市只需要条线路而每两个城市之间铺设管道都需要付出一定的经济代价而在个城市之间，最多可能铺设（）条管道，要在这些管道中选择条最少耗费的管道线路就可以转化为求最小生成树的问题一个生成数的代价就是树上各边的代价之合构造最小生成树可以有多种算法其中多数算法利用了最小生成树的性质：假设ga（，）是一个连通网，是顶点集的一个非空子集，若（u,v）是一条具有最小权值的边，其中u，v，则必存在一棵包含边（u,v）的最小生成树（证明略）普里姆(prim)算法就是利用这个性质构造最小生成树的算法假设ga=(V,E)是个连通网，是ga上的最小生成树边的集合算法从u0（u0V）,TE=开始，重复执行下面的操作：在所有的uU,vV-U的边（u,v）E中找一条代价最小的边（u0,v0）并入集合，同时v0并入U,直至U=V为止.此时TE中必有n-1条边,则T=(V,TE)为ga 上的最小生成树.在本题中根据题目要求首先需要重磁盘文件中读取任意两个居名区之间的铺设管道的代价,即知道了在由居名区构成的连通图中每条边的代价. 利用普里姆算法就可以求出最小生成树.Main() 主函数三.程序结构:(1) 流程图 函数关系载入数据 read_data()Prim( ) 生成最小边到lge 输出最小边的信息initalGraph () 初始化图形Line( )生成点的图形(2) 程序源码#include<stdio.h> #include<stdlib.h>#include<graphics.h> /* 需要用到的图形库 */#include<conio.h>#include<math.h>#define MAXVEX 12 /*常量的定义*/#define MAX 1000/* 图的定义*/typedef char VexType;typedef int AdjType;typedef struct AdjType arcsMAXVEXMAXVEX; int n;GraphMatrix;typedef struct int start_vex, stop_vex; /*最小边结构定义*/ AdjType weight;Edge;Edge lge12; int vex2=150,250,200,170,270,100,350,50,430,100,500,170,550,250,520,330,430,400,350,450,270,400,200,330; /*初始化 个顶点的坐标 */int info1212; char *text;void initalGraph(int vec2) /*画出顶点 函数*/ int gd=DETECT,gm; int i; initgraph(&gd,&gm,"d:TURBOC2"); setlinestyle(0,0,1); settextstyle(0,0,0); setbkcolor(9); for(i=0;i<12;i+) circle(veci0,veci1,12);/*画顶点圆*/ sprintf(text,"%c",65+i); outtextxy(veci0-1,veci1-1,text); /* 从字母A开始给顶点编号*/ printf("n");void read_data() /*从文件中读入权值数据*/ int i=0,j,q; FILE *fp; if(fp=fopen("info.txt","r")=NULL) printf("n This file can not be opened"); exit(0); while(!feof(fp) for(j=i+1;j<12;j+) fscanf(fp,"%d",&infoij); i+; fclose(fp);void prim(GraphMatrix * pgraph, Edge lge) /*普里姆算法主函数*/ int i, j, min, vx, vy; int weight, minweight; Edge edge; for(i=0; i<pgraph->n-1; i+) lgei.start_vex=0; lgei.stop_vex=i+1; lgei.weight=pgraph->arcs0i+1; for(i=0; i<pgraph->n-1; i+) minweight=MAX; min=i; for(j=i; j<pgraph->n-1; j+) if(lgej.weight<minweight) minweight=lgej.weight; min=j; edge=lgemin; lgemin=lgei; lgei=edge; vx=lgei.stop_vex; for(j=i+1; j<pgraph->n-1; j+) vy=lgej.stop_vex; weight=pgraph->arcsvxvy; if(weight<lgej.weight) lgej.weight=weight; lgej.start_vex=vx; 待添加的隐藏文字内容2 void main() int i; int j=0,k; int p,q; int gd=DETECT,gm; GraphMatrix graph; initgraph(&gd,&gm,"d:TURBOC"); read_data();/*读入数据*/ initalGraph(vex);/*图形初始化*/ for(j=0;j<12;j+) for(k=0;k<12;k+) graph.arcsjk=infojk; /*把info数组每边的权值附到图中*/ graph.n=12; prim(&graph,lge);for(i=0;i<graph.n-1;i+) printf("(%d %d %d)n",lgei.start_vex,lgei.stop_vex,lgei.weight); /* 输出N-1条最小边的信息*/ for(i=0;i<12;i+) line(vexlgei.start_vex0,vexlgei.start_vex1,vexlgei.stop_vex0,vexlgei.stop_vex1); /*根据生成的最小边数组连线*/printf("-It is done!-");getch(); exit(1);此程序再TURBOC2.0环境中编译通过运行.TURBOC2.0下载的地址四收获与体会尽管在大一学C的时候也做图形界面的程序,但是经过很长时间没有去用他,发现自己已经不是很熟悉了.这次的设计我又重新学习了C环境下图形函数的使用.在用普里姆算法做最小生成树的时候在不太理解的情况下又重新仔细的按照课本上的原理,充分研究了mst性质.并最终写出了Prim算法. 所以说每次的课程设计对我们计算机专业的学生来说时必要的,让我们逐渐写大的程序积累了宝贵的经验.特别是我发现程序还是要经常写,不然突然写起代码来会有点无从下手的感觉.
