1、離散數(shù)學實驗報告姓 名：學 號：班 級：實驗地點：實驗時間：1 實驗目的和要求運用最小生成樹思想和求最小生成樹程序解決實際問題。實際問題描述如下：八口海上油井相互間距離如下表，其中1號井離海岸最近，為5km。問從海岸經1號井鋪設油管把各井連接起來，怎樣連油管長度最短（為便于檢修，油管只準在油井處分叉）？從到234567811.32.10.90.71.82.01.820.91.81.22.82.31.132.61.72.51.91.040.71.61.50.950.91.10.860.61.070.52 實驗環(huán)境和工具實驗環(huán)境：Windows 7 旗艦版工具：Dev-C+ 5.8.33 實驗過程

2、開始3.1 算法流程圖結束int i,j;MGraph g;float AMAXV10;g.vexnum;在屏幕上打印運行結果Aij=INF;J<g.vexnumYdispMat(g);prim(g,0);i=0;j=0;g.vexnum=8;NY表中數(shù)據(jù)賦值給AMAXV10i<g.vexnumN3.2 程序核心代碼/油管鋪設問題 Prim算法實現(xiàn)#include <iostream>#include<iomanip>using namespace std;#define MAXV 10#define INF 32767 /INF表示typedef int

3、InfoType;typedef structint no; /頂點編號 InfoType info; /頂點其他信息 VertexType; /頂點類型typedef struct /圖的定義float edgesMAXVMAXV; /鄰接矩陣 int vexnum; /頂點數(shù) VertexType vexsMAXV; /存放頂點信息 MGraph; /圖的鄰接矩陣類型/*輸出鄰接矩陣g*/ void DispMat(MGraph g) int i,j; for (i=0;i<g.vexnum;i+) for (j=0;j<g.vexnum;j+) if (g.edgesij=I

4、NF) cout<<setw(6)<<"" else cout<<setw(6)<<g.edgesij; cout<<endl; void prim(MGraph g,int v) /從頂點V0出發(fā)，按Prim算法構造G的最小生成樹 /輸出最小生成樹的每條邊及其權值 float VlengthMAXV;int i, j, k;int cloestMAXV;float min;float sum = 0.0;for(i=0;i<g.vexnum;i+) Vlengthi=g.edgesvi; cloesti=v

5、; for(i=1;i<g.vexnum;i+) min=INF; /min為其中最大的一條邊=MAXV for(j=0;j<g.vexnum;j+) /找n-1條邊 if(Vlengthj!=0&&Vlengthj<min) min=Vlengthj; k=j; cout<<"連接油井<"<<cloestk+1<<","<<k+1<<">"<<"長度為:"<<min<<en

6、dl; sum+=min; Vlengthk=0; Vlengthcloestk=0;for(j=0;j<g.vexnum;j+) /選擇當前代價最小的邊 if(g.edgeskj!=0&&g.edgeskj<Vlengthj) Vlengthj=g.edgeskj; cloestj=k; cout<<"管道總長度為："<<sum<<endl; int main() int i,j,u=3; MGraph g; float AMAXV10; g.vexnum=8; for (i=0;i<g.vexnum;

7、i+) for (j=0;j<g.vexnum;j+) Aij=INF;A01=1.3; A02=2.1; A03=0.9;A04=0.7; A05=1.8; A06=2.0;A07=1.8; A12=0.9; A13=1.8;A14=1.2; A15=2.8; A16=2.3;A17=1.1; A23=2.6; A24=1.7;A25=2.5; A26=1.9; A27=1.0;A34=0.7; A35=1.6; A36=1.5;A37=0.9; A45=0.9; A46=1.1;A47=0.8; A56=0.6; A57=1.0;A67=0.5; for (i=0;i<g.ve

8、xnum;i+) for (j=0;j<g.vexnum;j+) Aji=Aij; for (i=0;i<g.vexnum;i+) /*建立圖的鄰接矩陣*/ for (j=0;j<g.vexnum;j+) g.edgesij=Aij; cout<<endl; cout<<"各油井間距離:n" DispMat(g); cout<<endl; cout<<"最優(yōu)鋪設方案:n" prim(g,0); cout<<endl; return 0;3.3 運行結果3.4 運行結果分析程序實現(xiàn)了輸出需要鋪設管道的油井編號，并給出了每條管道長度以及總長度，基本實現(xiàn)了題目要求。進一步優(yōu)化，根據(jù)用戶輸入的任意網絡的數(shù)據(jù)，在屏幕打印出管道連接的設計圖紙。4 實驗心得離散數(shù)學作為一門培養(yǎng)抽象思維、離