佛山科學(xué)技術(shù)學(xué)院

.@;

佛山科學(xué)技術(shù)學(xué)院

摘要：⑨廣度優(yōu)先搜索由鄰接矩陣函數(shù)voidbfsAdjoin()⑩求出用普里姆算法表示的圖的最小生成樹函數(shù)Prim()⑾求出用克魯斯卡爾算法表示的圖的最小生成樹函數(shù)Kruskal()...關(guān)鍵詞：矩陣,算法類別：專題技術(shù)來源：牛檔搜索（Niudown.COM）

本文系牛檔搜索（Niudown.COM）根據(jù)用戶的指令自動搜索的結(jié)果，文中內(nèi)涉及到的資料均來自互聯(lián)網(wǎng)，用于學(xué)習(xí)交流經(jīng)驗，作品其著作權(quán)歸原作者所有。不代表牛檔搜索（Niudown.COM）贊成本文的內(nèi)容或立場，牛檔搜索（Niudown.COM）不對其付相應(yīng)的法律責(zé)任！佛山科學(xué)技術(shù)學(xué)院實驗報告實驗名稱典型數(shù)據(jù)結(jié)構(gòu)算法實驗項目圖的最小生成樹專業(yè)班級08教育技術(shù)學(xué)（1）姓名楊李納學(xué)號2008914122指導(dǎo)教師容汝佳成績?nèi)掌?010.1.6一、實驗?zāi)康?．熟悉圖的鄰接矩陣、鄰接表表示。2．理解利用普里姆算法從頂點v。出發(fā)求出用鄰接矩陣GA表示的圖的最小生成樹.3.理解利用克魯斯卡爾方法求邊集數(shù)組GE所示圖的最小生成樹二、實驗內(nèi)容本實驗內(nèi)容的主要基本操作包括圖的鄰接矩陣、鄰接表表示以及圖的鄰接矩陣、鄰接表的利用克魯斯卡爾方法求邊集數(shù)組GE所示圖的最小生成樹利用普里姆算法從頂點v。出發(fā)求出用鄰接矩陣GA表示的圖的最小生成樹。三、實驗步驟1．需求分析輸入的形式：這個實驗主要是根據(jù)運行界面提示，在鍵盤上輸入相應(yīng)的數(shù)據(jù)：輸入待處理圖的頂點數(shù)，輸入無向帶權(quán)圖的每條邊的起點和終點序號及權(quán)值。eq\o\ac(○,2)輸出的形式：數(shù)據(jù)是以圖的邊集形式輸出的，把輸入的數(shù)據(jù)分別把利用普里姆算法和利用克魯卡爾方法所求出的最小生成樹相應(yīng)地輸出來。③程序所能達(dá)到的功能：這里在菜單控制下：實現(xiàn)數(shù)據(jù)的初始化、建立無向帶權(quán)圖的鄰接矩陣、輸出正確的結(jié)果。④測試數(shù)據(jù)：實驗結(jié)果詳見。2．概要設(shè)計1)基本操作：

voidIntiGMatrix(adjmatrix&GA,intn)操作結(jié)果：初始化圖的鄰接矩陣.

voidCreateMatrix(adjmatrixGA,intn,intk1,intk2);

初始條件：鄰接矩陣已存在

操作結(jié)果：建立圖的鄰接矩陣voidInitGEdge(edgeset&GE,inte)操作結(jié)果:建立圖的邊集數(shù)組voidChangeEdgeSet(adjmatrixGA,edgesetGE,intn,inte)初始條件：邊集數(shù)組已存在

操作結(jié)果：根據(jù)圖的鄰接矩陣生成圖的邊集數(shù)組voidIntiGAdjoin(adjlist&GL,intn)

初始條件：鄰接表已存在

操作結(jié)果：初始鄰接表voidCreateAdjoin(adjlist&GL,intn,intk1,intk2)初始條件：鄰接表已存在

操作結(jié)果：建立鄰接表voidSortEdgeSet(edgesetGE,inte)初始條件：鄰接表已存在

操作結(jié)果：按升序排列圖的邊集數(shù)組voidPrim(adjmatrixGA,edgesetCT,intn)初始條件：鄰接矩陣已存在

操作結(jié)果：求出用鄰接矩陣GA表示的圖的最小生成樹voidKruskal(edgesetGE,edgesetC,intn)初始條件：邊集數(shù)組已存在

操作結(jié)果：求邊集數(shù)組GE所示圖的最小生成樹2）本程序包含8個函數(shù)：

①主函數(shù)main()

②初始化圖的鄰接矩陣函數(shù)voidIntiGMatrix③建立圖的鄰接矩陣表函數(shù)oidCreateMatrix()

④建立圖的邊集數(shù)組函數(shù)InitGEdge()⑤根據(jù)圖的鄰接矩陣生成圖的邊集數(shù)組函數(shù)ChangeEdgeSet()⑥初始鄰接表函數(shù)voidIntiGAdjoin(）⑦建立鄰接表函數(shù)voidCreateAdjoin()

⑧按升序排列圖的邊集數(shù)組函數(shù)voidSortEdgeSet()⑨廣度優(yōu)先搜索由鄰接矩陣函數(shù)voidbfsAdjoin()⑩求出用普里姆算法表示的圖的最小生成樹函數(shù)Prim()⑾求出用克魯斯卡爾算法表示的圖的最小生成樹函數(shù)Kruskal()各函數(shù)間關(guān)系如下：

3．詳細(xì)設(shè)計實現(xiàn)概要設(shè)計中定義的所有的數(shù)據(jù)類型，對每個操作給出算法代碼。對主程序和其他模塊也都需要寫出算法的C++代碼。

1)包含文件說明部分:

#include<iostream.h>#include<stdlib.h>constintMaxValue=10000;2)元素類型和結(jié)構(gòu)類型說明部分:

//定義鄰接矩陣類型typedefint**adjmatrix;//定義鄰接表中的邊結(jié)點類型structedgenode{ intadjvex;//鄰接點域 intweight;//權(quán)值域 edgenode*next;//指向下一個邊結(jié)點的鏈域};//定義鄰接表類型typedefedgenode**adjlist;//定義邊集數(shù)組中的元素類型structedge{ intfromvex;//起點域 intendvex;//終點域 intweight;//權(quán)域};//定義邊集數(shù)組的類型typedefedge*edgeset;3)基本操作的實現(xiàn)voidCheck(intn,int&i,int&j);voidInitGEdge(edgeset&GE,inte){ GE=newedge[e]; for(inti=0;i<e;i++) GE[i].weight=0;}voidOutputEdgeSet(edgesetGE,inte){ cout<<'{'; for(inti=0;i<=e-2;i++) { cout<<'('<<GE[i].fromvex<<','<<GE[i].endvex<<')'; cout<<GE[i].weight<<","; } if(e>0) { cout<<'('<<GE[e-1].fromvex<<','<<GE[e-1].endvex<<')'; cout<<GE[e-1].weight<<''; } cout<<'}'<<endl;}voidInitGAdjoin(adjlist&GL,intn){ GL=newedgenode*[n]; for(inti=0;i<n;i++) GL[i]=NULL;}voidDeleteAdjoin(adjlistGL,intn){ inti; edgenode*p; for(i=0;i<n;i++) p=GL[i]; while(p!=NULL) { GL[i]=p->next;deletep;p=GL[i]; } delete[]GL;}voidInitGMatrix(adjmatrix&GA,intn){ GA=newint*[n]; inti,j; for(i=0;i<n;i++) GA[i]=newint[n]; for(i=0;i<n;i++) for(j=0;j<n;j++)if(i==j)GA[i][j]=0; elseGA[i][j]=MaxValue;}voidCreateMatrix(adjmatrixGA,intn,int&e){ inti,j,k=0,w; cout<<"依次輸入無向帶權(quán)圖的每條邊的起點和終點序號及權(quán)值!"<<endl; cout<<"直到輸入權(quán)植為0的邊為止"<<endl; do { cin>>i>>j>>w; Check(n,i,j); if(w==0)break; GA[i][j]=GA[j][i]=w; k++; } while(1); e=k;}voidCheck(intn,int&i,int&j){ while(1) { if(i<0||i>=n||j<0||j>=n) cout<<"輸入有誤,請重輸!"; elsereturn; cin>>i>>j; }}voidgraphChange(adjmatrixGA,adjlistGL,intn){ inti,j; for(i=0;i<n;i++) { for(j=0;j<n;j++) { if(GA[i][j]!=0&&GA[i][j]!=MaxValue) { edgenode*p=newedgenode; p->adjvex=j; p->weight=GA[i][j]; p->next=GL[i]; GL[i]=p; } } }}voidChangeEdgeSet(adjmatrixGA,edgesetGE,intn,inte){ inti,j,k=0; for(i=0;i<n;i++) for(j=i+1;j<n;j++) if(GA[i][j]!=0&&GA[i][j]!=MaxValue) { if(k==e) { cout<<"數(shù)組GE下標(biāo)越界!"<<endl; exit(1); } GE[k].fromvex=i; GE[k].endvex=j; GE[k].weight=GA[i][j]; k++; }}voidSortEdgeSet(edgesetGE,inte){ inti,j; edgex; for(i=1;i<=e-1;i++) { x=GE[i]; for(j=i-1;j>=0;j--) if(x.weight<GE[j].weight) GE[j+1]=GE[j]; elsebreak; GE[j+1]=x; }}voidPrim(adjmatrixGA,edgesetCT,intn){ inti,j,k,min,t,m,w; for(i=0;i<n-1;i++) { CT[i].fromvex=0; CT[i].endvex=i+1; CT[i].weight=GA[0][i+1]; } for(k=1;k<n;k++) { min=MaxValue; m=k-1; for(j=k-1;j<n-1;j++) if(CT[j].weight<min) { min=CT[j].weight; m=j; } edgetemp=CT[k-1]; CT[k-1]=CT[m]; CT[m]=temp; j=CT[k-1].endvex; for(i=k;i<n-1;i++) { t=CT[i].endvex; w=GA[j][t]; if(w<CT[i].weight) { CT[i].weight=w; CT[i].fromvex=j; } } }}voidKruskal(edgesetGE,edgesetC,intn){ inti; edgenode*p; adjlists; InitGAdjoin(s,n); for(i=0;i<n;i++) { p=newedgenode; p->adjvex=i;p->next=NULL; s[i]=p; } intk=1; intd=0; intm1,m2; while(k<n) { for(i=0;i<n;i++) { p=s[i]; while(p!=NULL) { if(p->adjvex==GE[d].fromvex)m1=i; if(p->adjvex==GE[d].endvex)m2=i; p=p->next; } } if(m1!=m2) { C[k-1]=GE[d]; k++; p=s[m1]; while(p->next!=NULL) p=p->next; p->next=s[m2]; s[m2]=NULL; } d++; }} （四）、主函數(shù)的實現(xiàn)voidmain(){ intn,EdgeNum; cout<<"輸入待處理圖的頂點數(shù):"; cin>>n;//定義一個鄰接矩陣ga并初始化 adjmatrixga; InitGMatrix(ga,n);//根據(jù)鍵盤輸入建立一個鄰接矩陣gaCreateMatrix(ga,n,EdgeNum); //定義一個邊集數(shù)組ge并初始化edgesetge; InitGEdge(ge,EdgeNum); //根據(jù)圖的鄰接矩陣ga得到圖的邊集數(shù)組geChangeEdgeSet(ga,ge,n,EdgeNum); //利用普里姆算法求圖ga的最小生成樹edgesetct; InitGEdge(ct,n); Prim(ga,ct,n); //輸出ct中保存的最小生成樹中的每條邊OutputEdgeSet(ct,n-1); //利用克魯斯卡爾方法求ge讓所示圖的最小生成樹SortEdgeSet(ge,EdgeNum); Kruskal(ge,ct,n)