《数据结构》课程设计 普里姆算法 最小生成树.doc

《数据结构》课程设计报告 蔡金林一．设计课题： 管道铺设施工的最佳方案选择. N (N10)个居名之间需要铺设煤气管道.假设任意两个居名之间都可以铺设煤气管道,但代价不同.事先将任意两个居名之间铺设煤气管道的代价存入磁盘文件中.设计一个最佳方案使得这N个居名之间铺设煤气管道所需要代价最少,并希望以图形方式在屏幕上输出结果。 二．算法思想： 要在Ｎ个城市之间铺设煤气管道，则连通Ｎ个城市只需要Ｎ－１条线路．而每两个城市之间铺设管道都需要付出一定的经济代价．而在Ｎ个城市之间，最多可能铺设Ｎ（Ｎ－１）／２条管道，要在这些管道中选择Ｎ－１条最少耗费的管道线路就可以转化为求最小生成树的问题．一个生成数的代价就是树上各边的代价之合． 构造最小生成树可以有多种算法．其中多数算法利用了最小生成树的ＭＳＴ性质：假设ga＝（Ｖ，｛Ｅ｝）是一个连通网，Ｕ是顶点集Ｖ的一个非空子集，若（u,v）是一条具有最小权值的边，其中u∈Ｕ，v∈Ｖ－Ｕ，则必存在一棵包含边（u,v）的最小生成树．（证明略） 普里姆(prim)算法就是利用这个性质构造最小生成树的算法． 假设ga=(V,{E})是个连通网，ＴＥ是ga上的最小生成树边的集合．算法从Ｕ＝｛u0｝（u0∈V）,TE={}开始，重复执行下面的操作：在所有的u∈U,v∈V-U的边（u,v）∈E中找一条代价最小的边（u0,v0）并入集合ＴＥ，同时v0并入U,直至U=V为止.此时TE中必有n-1条边,则T=(V,{TE})为ga 上的最小生成树. 在本题中根据题目要求首先需要重磁盘文件中读取任意两个居名区之间的铺设管道的代价,即知道了在由居名区构成的连通图中每条边的代价. 利用普里姆算法就可以求出最小生成树. 三.程序结构: 流程图 函数关系 (2) 程序源码 #includestdio.h #includestdlib.h #includegraphics.h /* 需要用到的图形库 */ #includeconio.h #includemath.h #define MAXVEX 12 /*常量的定义*/ #define MAX 1000 /* 图的定义*/ typedef char VexType; typedef int AdjType; typedef struct { AdjType arcs[MAXVEX][MAXVEX]; int n; }GraphMatrix; typedef struct{ int start_vex, stop_vex; /*最小边结构定义*/ AdjType weight; }Edge; Edge lge[12]; int vex[][2]={{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 info[12][12]; char *text; void initalGraph(int vec[][2]) /*画出顶点 函数*/ { int gd=DETECT,gm; int i; initgraph(gd,gm,d:\\TURBOC2); setlinestyle(0,0,1); settextstyle(0,0,0); setbkcolor(9); for(i=0;i12;i++) { circle(vec[i][0],vec[i][1],12);/*画顶点圆*/ sprintf(text,%c,65+i); outtextxy(vec[i][0]-1,vec[i][1]-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;j12;j++) { fscanf(fp,%d,info[i][j]); } i++; } fclose(fp); } void prim(GraphMatri