國(guó)家開(kāi)放大學(xué)《數(shù)據(jù)結(jié)構(gòu)》課程實(shí)驗(yàn)報(bào)告(實(shí)驗(yàn)5-圖的存儲(chǔ)方式和應(yīng)用)參考答案

《數(shù)據(jù)結(jié)構(gòu)》課程實(shí)驗(yàn)報(bào)告（實(shí)驗(yàn)5——圖的存儲(chǔ)方式和應(yīng)用）學(xué)生姓名

學(xué)

號(hào)班

級(jí)

指導(dǎo)老師實(shí)驗(yàn)名稱

實(shí)驗(yàn)成績(jī)實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)?zāi)康模焊鶕?jù)圖中頂點(diǎn)和邊的信息編制程序建立圖的鄰接矩陣。實(shí)驗(yàn)概述實(shí)

實(shí)驗(yàn)要求：（1）程序要有一定的通用性。（2）直接根據(jù)圖中每個(gè)結(jié)點(diǎn)與其他結(jié)點(diǎn)的關(guān)聯(lián)情況輸入相關(guān)信息，程序能自動(dòng)形成鄰接矩陣。實(shí)驗(yàn)基本原理：（1）為保證程序的通用性，適合各種圖，在建立圖的鄰接矩陣算法中增加兩個(gè)參數(shù)k1和k2。k1為0表示無(wú)向圖，否則為有向圖；k2為0表示邊上無(wú)權(quán)，否則為邊上有權(quán)。（2）初始化鄰接矩陣時(shí)，對(duì)角線元素設(shè)置為0。若圖的邊上有權(quán)，則其他元素值設(shè)為∞；若邊上無(wú)權(quán)，則設(shè)為0。程序代碼：/*實(shí)驗(yàn)4.1建立圖的鄰接矩陣*/#include<stdio.h>驗(yàn)內(nèi)容

#defineMaxVertexNum8#defineMaxEdgeNum20#defineMaxValue1000

/*定義圖的最大頂點(diǎn)數(shù)*//*定義圖的最大邊數(shù)*//*定義相當(dāng)于∞的常量值*/typedefintVertexType;/*定義頂點(diǎn)數(shù)據(jù)類型VertexType為整型*/typedefVertexTypevexlist[MaxVertexNum];/*定義vexlist為存儲(chǔ)頂點(diǎn)信息的數(shù)組類型*/typedefintadjmatrix[MaxVertexNum][MaxVertexNum];/*定義adjmatrix為存儲(chǔ)鄰接矩陣的數(shù)組類型*/voidCreateMatrix(vexlistGV,adjmatrixGA,intn,inte,intk1,intk2);

/*建立圖的鄰接矩陣*/voidShowMatrix(vexlistGV,adjmatrixGA,intn);/*輸出圖的鄰接矩陣*/voidmain(){intn,e,k1,k2;vexlistgv;/*定義保存頂點(diǎn)信息的數(shù)組*/adjmatrixga;

/*定義保存鄰接矩陣的數(shù)組*//*輸入一個(gè)圖的頂點(diǎn)數(shù)和邊數(shù)*/printf("輸入待處理圖的頂點(diǎn)數(shù)和邊數(shù)：");scanf("%d%d",&n,&e);/*輸入有無(wú)向選擇和有無(wú)權(quán)選擇*/printf("輸入有無(wú)向選擇和有無(wú)權(quán)選擇（0為無(wú)，非0為有）：");scanf("%d%d",&k1,&k2);CreateMatrix(gv,ga,n,e,k1,k2);/*建立圖的鄰接矩陣*/printf("\n圖的鄰接矩陣為：\n\n");ShowMatrix(gv,ga,n);

/*輸出圖的鄰接矩陣*/}/*輸入n個(gè)頂點(diǎn)和e條邊，建立圖的鄰接矩陣*/voidCreateMatrix(vexlistGV,adjmatrixGA,intn,inte,intk1,intk2){/*k1為0則無(wú)向，否則為有向；k2為0則無(wú)權(quán)，否則為有權(quán)*/inti,j,k,w;/*建立頂點(diǎn)數(shù)組*/printf("輸入%d個(gè)頂點(diǎn)數(shù)據(jù)：",n);for(i=0;i<n;i++)scanf("%d",&GV[i]);/*初始化圖的鄰接矩陣*/for(i=0;i<n;i++)for(j=0;j<n;j++){if(i==j)GA[i][j]=0;elseif(k2!=0)GA[i][j]=MaxValue;elseGA[i][j]=0;}if(k1==0&&k2==0)

/*建立無(wú)向無(wú)權(quán)圖*/{printf("輸入%d條無(wú)向無(wú)權(quán)邊的起點(diǎn)和終點(diǎn)序號(hào)！\n",e);for(k=1;k<=e;k++){scanf("%d%d",&i,&j);GA[i][j]=GA[j][i]=1;}}elseif(k1==0&&k2!=0)/*建立無(wú)向有權(quán)圖*/{printf("輸入%d條無(wú)向有權(quán)邊的起點(diǎn)和終點(diǎn)序號(hào)及權(quán)值！\n",e);for(k=1;k<=e;k++){scanf("%d%d%d",&i,&j,&w);GA[i][j]=GA[j][i]=w;}}elseif(k1!=0&&k2==0)/*建立有向無(wú)權(quán)圖*/{printf("輸入%d條有向無(wú)權(quán)邊的起點(diǎn)和終點(diǎn)序號(hào)！\n",e);for(k=1;k<=e;k++){scanf("%d%d",&i,&j);GA[i][j]=1;}}elseif(k1!=0&&k2!=0)/*建立有向有權(quán)圖*/{printf("輸入%d條有向有權(quán)邊的起點(diǎn)和終點(diǎn)序號(hào)及權(quán)值！\n",e);for(k=1;k<=e;k++){scanf("%d%d%d",&i,&j,&w);GA[i][j]=w;}}}/*輸出圖的鄰接矩陣*/voidShowMatrix(vexlistGV,adjmatrixGA,intn){inti,j;printf("

頂點(diǎn)");for(i=0;i<n;i++)printf("%6d",GV[i]);printf("\n");for(i=0;i<n;i++){printf("%6d",GV[i]);for(j=0;j<n;j++){if(GA[i][j]==MaxValue)printf("%6s","∞");elseprintf("%6d",GA[i][j]);}printf("\n");}}實(shí)驗(yàn)結(jié)果：測(cè)試用例1無(wú)向無(wú)權(quán)圖如下圖所示。程序運(yùn)行結(jié)果如下：測(cè)試用例2有向有權(quán)圖如下圖所示。程序運(yùn)行結(jié)果如下：（1）具有n個(gè)頂點(diǎn)的圖，其鄰接矩陣為