《數據結構》課程設計 普里姆算法 最小生成樹.doc

課程設計 管道鋪設施工的最佳方案選擇 18031944 數據結構課程設計報告蔡金林18031944一設計課題：管道鋪設施工的最佳方案選擇.N (N10)個居名之間需要鋪設煤氣管道.假設任意兩個居名之間都可以鋪設煤氣管道,但代價不同.事先將任意兩個居名之間鋪設煤氣管道的代價存入磁盤文件中.設計一個最佳方案使得這N個居名之間鋪設煤氣管道所需要代價最少,并希望以圖形方式在屏幕上輸出結果。二算法思想：要在個城市之間鋪設煤氣管道，則連通個城市只需要條線路而每兩個城市之間鋪設管道都需要付出一定的經濟代價而在個城市之間，最多可能鋪設（）條管道，要在這些管道中選擇條最少耗費的管道線路就可以轉化為求最小生成樹的問題一個生成數的代價就是樹上各邊的代價之合構造最小生成樹可以有多種算法其中多數算法利用了最小生成樹的性質：假設ga（，）是一個連通網，是頂點集的一個非空子集，若（u,v）是一條具有最小權值的邊，其中u，v，則必存在一棵包含邊（u,v）的最小生成樹（證明略）普里姆(prim)算法就是利用這個性質構造最小生成樹的算法假設ga=(V,E)是個連通網，是ga上的最小生成樹邊的集合算法從u0（u0V）,TE=開始，重復執(zhí)行下面的操作：在所有的uU,vV-U的邊（u,v）E中找一條代價最小的邊（u0,v0）并入集合，同時v0并入U,直至U=V為止.此時TE中必有n-1條邊,則T=(V,TE)為ga 上的最小生成樹.在本題中根據題目要求首先需要重磁盤文件中讀取任意兩個居名區(qū)之間的鋪設管道的代價,即知道了在由居名區(qū)構成的連通圖中每條邊的代價. 利用普里姆算法就可以求出最小生成樹.Main() 主函數三.程序結構:(1) 流程圖 函數關系載入數據 read_data()Prim( ) 生成最小邊到lge 輸出最小邊的信息initalGraph () 初始化圖形Line( )生成點的圖形(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; /*最小邊結構定義*/ 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;i12;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;j12;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; 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();/*讀入數據*/ initalGraph(vex);/*圖形初始化*/ for(j=0;j12;j+) for(k=0;k12;k+) graph.arcsjk=infojk; /*把info數組每邊的權值附到圖中*/ 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); /*根據生成的最小邊數組連線*/printf(-It is done!-);getch(); exit(1);此程序再TURBOC2.0環(huán)境中編譯通過運行.TURBOC2.0下載的地址/downloads/tc2.rar四收獲與體會盡管在大一學C的時候也做圖形界面的程序,但是經過很長時間沒有去用他,發(fā)現自己已經不是很熟悉了.這次的設計我又重新學習了C環(huán)境下圖形函數的使用.在用普里姆算法做最小生成樹的時候在不太理解的情況下又重