《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì) 普里姆算法 最小生成樹.doc

課程設(shè)計(jì) 管道鋪設(shè)施工的最佳方案選擇 18031944 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告蔡金林18031944一設(shè)計(jì)課題：管道鋪設(shè)施工的最佳方案選擇.N (N10)個(gè)居名之間需要鋪設(shè)煤氣管道.假設(shè)任意兩個(gè)居名之間都可以鋪設(shè)煤氣管道,但代價(jià)不同.事先將任意兩個(gè)居名之間鋪設(shè)煤氣管道的代價(jià)存入磁盤文件中.設(shè)計(jì)一個(gè)最佳方案使得這N個(gè)居名之間鋪設(shè)煤氣管道所需要代價(jià)最少,并希望以圖形方式在屏幕上輸出結(jié)果。二算法思想：要在個(gè)城市之間鋪設(shè)煤氣管道，則連通個(gè)城市只需要條線路而每兩個(gè)城市之間鋪設(shè)管道都需要付出一定的經(jīng)濟(jì)代價(jià)而在個(gè)城市之間，最多可能鋪設(shè)（）條管道，要在這些管道中選擇條最少耗費(fèi)的管道線路就可以轉(zhuǎn)化為求最小生成樹的問題一個(gè)生成數(shù)的代價(jià)就是樹上各邊的代價(jià)之合構(gòu)造最小生成樹可以有多種算法其中多數(shù)算法利用了最小生成樹的性質(zhì)：假設(shè)ga（，）是一個(gè)連通網(wǎng)，是頂點(diǎn)集的一個(gè)非空子集，若（u,v）是一條具有最小權(quán)值的邊，其中u，v，則必存在一棵包含邊（u,v）的最小生成樹（證明略）普里姆(prim)算法就是利用這個(gè)性質(zhì)構(gòu)造最小生成樹的算法假設(shè)ga=(V,E)是個(gè)連通網(wǎng)，是ga上的最小生成樹邊的集合算法從u0（u0V）,TE=開始，重復(fù)執(zhí)行下面的操作：在所有的uU,vV-U的邊（u,v）E中找一條代價(jià)最小的邊（u0,v0）并入集合，同時(shí)v0并入U(xiǎn),直至U=V為止.此時(shí)TE中必有n-1條邊,則T=(V,TE)為ga 上的最小生成樹.在本題中根據(jù)題目要求首先需要重磁盤文件中讀取任意兩個(gè)居名區(qū)之間的鋪設(shè)管道的代價(jià),即知道了在由居名區(qū)構(gòu)成的連通圖中每條邊的代價(jià). 利用普里姆算法就可以求出最小生成樹.Main() 主函數(shù)三.程序結(jié)構(gòu):(1) 流程圖 函數(shù)關(guān)系載入數(shù)據(jù) read_data()Prim( ) 生成最小邊到lge 輸出最小邊的信息initalGraph () 初始化圖形Line( )生成點(diǎn)的圖形(2) 程序源碼#include #include#include /* 需要用到的圖形庫 */#include#include#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; /*最小邊結(jié)構(gòu)定義*/ 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; /*初始化 個(gè)頂點(diǎn)的坐標(biāo) */int info1212; char *text;void initalGraph(int vec2) /*畫出頂點(diǎn) 函數(shù)*/ 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(veci0,veci1,12);/*畫頂點(diǎn)圓*/ sprintf(text,%c,65+i); outtextxy(veci0-1,veci1-1,text); /* 從字母A開始給頂點(diǎn)編號(hào)*/ printf(n);void read_data() /*從文件中讀入權(quán)值數(shù)據(jù)*/ 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,&infoij); i+; fclose(fp);void prim(GraphMatrix * pgraph, Edge lge) /*普里姆算法主函數(shù)*/ int i, j, min, vx, vy; int weight, minweight; Edge edge; for(i=0; in-1; i+) lgei.start_vex=0; lgei.stop_vex=i+1; lgei.weight=pgraph-arcs0i+1; for(i=0; in-1; i+) minweight=MAX; min=i; for(j=i; jn-1; j+) if(lgej.weightminweight) minweight=lgej.weight; min=j; edge=lgemin; lgemin=lgei; lgei=edge; vx=lgei.stop_vex; for(j=i+1; jn-1; j+) vy=lgej.stop_vex; weight=pgraph-arcsvxvy; if(weightlgej.weight) lgej.weight=weight; lgej.start_vex=vx; void main() int i; int j=0,k; int p,q; int gd=DETECT,gm; GraphMatrix graph; initgraph(&gd,&gm,d:TURBOC); read_data();/*讀入數(shù)據(jù)*/ initalGraph(vex);/*圖形初始化*/ for(j=0;j12;j+) for(k=0;k12;k+) graph.arcsjk=infojk; /*把info數(shù)組每邊的權(quán)值附到圖中*/ graph.n=12; prim(&graph,lge);for(i=0;igraph.n-1;i+) printf(%d %d %d)n,lgei.start_vex,lgei.stop_vex,lgei.weight); /* 輸出N-1條最小邊的信息*/ for(i=0;i12;i+) line(vexlgei.start_vex0,vexlgei.start_vex1,vexlgei.stop_vex0,vexlgei.stop_vex1); /*根據(jù)生成的最小邊數(shù)組連線*/printf(-It is done!-);getch(); exit(1);此程序再TURBOC2.0環(huán)境中編譯通過運(yùn)行.TURBOC2.0下載的地址/downloads/tc2.rar四收獲與體會(huì)盡管在大一學(xué)C的時(shí)候也做圖形界面的程序,但是經(jīng)過很長時(shí)間沒有去用他,發(fā)現(xiàn)自己已經(jīng)不是很熟悉了.這次的設(shè)計(jì)我又重新學(xué)習(xí)了C環(huán)境下圖形函數(shù)的使用.在用普里姆算法做最小生成樹的時(shí)候在不太理解的情況下又重