實驗十二圖的基本操作—鄰接矩陣存儲結構

1、浙江大學城市學院實驗報告課程名稱 數據結構基礎 實驗項目名稱 實驗十二 圖的基本操作鄰接矩陣存儲結構 學生姓名 專業(yè)班級 學號 實驗成績 指導老師（簽名 ） 日期 一. 實驗目的和要求1、掌握圖的存儲結構：鄰接矩陣。2、學會對圖的存儲結構進行基本操作。二. 實驗內容1、圖的鄰接矩陣定義及實現：建立頭文件adjmatrix.h，在該文件中定義圖的鄰接矩陣存儲結構，并編寫圖的初始化、建立圖、輸出圖、輸出圖的每個頂點的度等基本操作實現函數。同時建立一個驗證操作實現的主函數文件test5_1.cpp，編譯并調試程序，直到正確運行。 2、選做：編寫圖的深度優(yōu)先遍歷函數與廣度優(yōu)先遍歷函數，要求把這兩個函數

2、添加到頭文件adjmatrix.h中，并在主函數文件test5_1.cpp中添加相應語句進行測試。3、填寫實驗報告，實驗報告文件取名為report12.doc。4、上傳實驗報告文件report12.doc及源程序文件test5_1.cpp、adjmatrix.h到ftp服務器上自己的文件夾下。三. 函數的功能說明及算法思路 （包括每個函數的功能說明，及一些重要函數的算法實現思路）鄰接矩陣表示法的c語言描述：typedef structvexlist vexs; /頂點數據元素adjmatrix ga; /二維數組作鄰接矩陣int n; /頂點數int k1,k2; /k1為有無向，k2為有無權

3、graph;const int maxvertexnum = 10; /*圖的最大頂點數*/const int maxedgenum = 100; /*圖的最大邊數*/const int maxvalue = 10000; /*無窮大的具體值*/typedef int weighttype; /*定義權的類型*/typedef char vertextype;typedef vertextype vexlistmaxvertexnum; /*定義頂點數組類型*/typedef int adjmatrixmaxvertexnummaxvertexnum; /*定義鄰接矩陣類型*/抽象數據類型：a

4、dt graph is data: graph(v, e ) 其中： v = vi | 0=i=0, vi vertextype 是頂點的有窮集合； e = (x, y) | x, y v 或 e = | x, y v 是頂點之間關系的有窮集合，也叫做邊集合。 存儲類型用adjmatrix表示 operations: void initmatrix( adjmatrix ga, int k)/初始化算法（假設頂點信息僅是序號） void creatematrix( adjmatrix ga, int n, char *s, int k1, int k2)/建立圖的鄰接矩陣算法 void pri

5、ntmatrix( adjmatrix ga, int n, int k1, int k2)/根據圖的鄰接矩陣輸出圖的頂點集和邊集 void printdegree(vexlist v,adjmatrix ga,int n,int k1)/計算各個頂點的度 void dfsmatrix(adjmatrix ga,int i,int n,bool *visited)/深度優(yōu)先遍歷 void bfsmatrix( adjmatrix ga,int i,int n,bool *visited)/廣度優(yōu)先遍歷end度的算法：void printdegree(vexlist v,adjmatrix ga

6、,int n,int k1)數組vi存放所有頂點，根據邊結點的指針數組計算該結點的度;若圖是有向圖，則查找所有邊結點的鄰接點域，如果是當前結點的位置，就將該結點對應的度+1。隊列：typedef char elemtype;struct queueelemtype *queue;int front,rear;int maxsize;operations:void initqueue(queue &q) /初始化循環(huán)隊列qint emptyqueue(queue q)/判斷隊列是否為空，空返回1，否則返回0void enqueue(queue &q,elemtype item)/ 入隊列elem

7、type outqueue(queue &q) / 出隊列end queue四. 實驗結果與分析（包括運行結果截圖、結果分析等）無向無權圖：無向有權圖：有向無權圖：有向有權圖：五. 心得體會（記錄實驗感受、上機過程中遇到的困難及解決辦法、遺留的問題、意見和建議等。）在計算度的編程上出現了問題，計算void printdegree(vexlist v,adjmatrix ga,int n,int k1)時，vi是存放頂點的數組，但是在main()函數里面忘記使用數組，結果編譯是正確的但是輸出來是一堆亂碼。最后改了好久才想起來，在前面加上cout請輸入圖的頂點集合(如:abc)endl;for(i

8、=0; ig.vexsi;【附錄-源程序】test5_1.cpp：#include#include#include#include#includeconst int maxvertexnum = 10; /*圖的最大頂點數*/const int maxedgenum = 100; /*圖的最大邊數*/const int maxvalue = 10000; /*無窮大的具體值*/typedef int weighttype; /*定義權的類型*/typedef char vertextype;typedef vertextype vexlistmaxvertexnum; /*定義頂點數組類型*/

9、typedef int adjmatrixmaxvertexnummaxvertexnum; /*定義鄰接矩陣類型*/#include adjmatrix.h void main()graph g;/鄰接矩陣int i;coutg.n;cout請輸入圖的頂點集合(如:abc)endl;for(i=0; ig.vexsi;coutg.k1g.k2;bool *visited=new boolg.n; /定義并動態(tài)分配標志數組initmatrix(g.ga,g.k2);couta;creatematrix(g.ga,g.n,a,g.k1,g.k2);printdegree(g.vexs,g.ga,

10、g.n,g.k1);cout按圖的鄰接矩陣得到的深度優(yōu)先遍歷序列:endl;for(i=0;ig.n;i+) visitedi=false;dfsmatrix(g.ga,0,g.n,visited);coutendl;cout按圖的鄰接矩陣得到的廣度優(yōu)先遍歷序列:endl;for(i=0;ig.n;i+) visitedi=false;bfsmatrix(g.ga,0,g.n,visited);coutendl;printmatrix(g.ga,g.n,g.k1,g.k2);adjmatrix.htypedef structvexlist vexs; /頂點數據元素adjmatrix ga;

11、/二維數組作鄰接矩陣int n; /頂點數int k1,k2; /k1為有無向，k2為有無權graph;void initmatrix( adjmatrix ga, int k)/初始化算法 （假設頂點信息僅是序號）/k=0代表無權圖，k0代表帶權圖int i, j;for( i=0; imaxvertexnum; i+)for( j=0; jc1; /讀入第一個字符 if(k1=0 & k2=0) /建立無向無權圖dosinc1ic2jc3; /讀入一條邊，如 (2,5) gaij = gaji = 1; /相應的邊元素置1 sinc1; /讀入, 或 if (c1=) break;whil

12、e (1);else if (k1=0 & k2!=0) /建立無向帶權圖dosinc1ic2jc3w; /讀入一條邊，如 (2,5)8gaij = gaji = w;sinc1;if (c1=) break;while(1);else if (k1!=0 & k2=0) /建立有向無權圖do sinc1ic2jc3;gaij = 1; sinc1;if (c1=) break;while(1);else if (k1!=0 & k2!=0) /建立有向帶權圖do sinc1ic2jc3w;gaij = w;sinc1;if (c1=) break;while(1);void printmat

13、rix( adjmatrix ga, int n, int k1, int k2)/根據圖的鄰接矩陣輸出圖的頂點集和邊集/ k1=0 代表無向圖否則為有向圖, k2 =0 代表無權圖否則為帶權圖int i, j;cout v=; /準備輸出頂點集for(i=0; in-1; i+)couti,;coutn-1endl;cout e=; /準備輸出邊集if(k2=0) /無權圖 for(i=0; in; i+)for(j=0; jn; j+)if( gaij =1 )if(k1=0) /無向圖if(ij)cout(i,j),;else /有向圖couti,j,;else /帶權圖 for(i=0

14、; in; i+)for(j=0; jn; j+)if(gaij != 0 & gaij != maxvalue )if(k1=0) /無向圖if(ij)cout(i,j)gaij,;else /有向圖couti,j gaij,;coutendl; void printdegree(vexlist v,adjmatrix ga,int n,int k1)/計算各個頂點的度int i,j,d;for(i=0;in;i+)d=0;for(j=0;jn;j+)if(gaij!=0&gaij!=maxvalue)d+;if(k1) /有向圖for(j=0;jn;j+)if(gaji!=0&gaji!=

15、maxvalue)d+;coutvi的度為dendl;/*=選作部分=*/typedef char elemtype;struct queueelemtype *queue;int front,rear;int maxsize;void initqueue(queue &q) /初始化循環(huán)隊列qq.maxsize=10;q.queue=(elemtype *)malloc(sizeof(elemtype)*q.maxsize);q.rear=q.front=0;int emptyqueue(queue q)/判斷隊列是否為空，空返回1，否則返回0return q.front=q.rear;vo

16、id enqueue(queue &q,elemtype item)/ 入隊列if(q.rear+1) % q.maxsize = q.front)/若隊列已滿，重新分配2倍大的空間q.queue=(elemtype *)realloc(q.queue,2*q.maxsize*sizeof(elemtype);if(q.rear != q.maxsize-1) /原隊列尾部內容向后移for(int i=0; i=q.rear; i+)q.queuei+q.maxsize = q.queuei;q.rear=q.rear+q.maxsize;q.maxsize=2*q.maxsize; / 插入

17、itemq.rear=(q.rear+1)%q.maxsize;q.queueq.rear=item;elemtype outqueue(queue &q) / 出隊列if(q.front=q.rear) /若空隊列，則結束運行cerr 隊列已空，無法刪除! endl;exit(1); /刪除隊頭元素，并返回該元素q.front=(q.front +1)%q.maxsize;return q.queueq.front;void dfsmatrix(adjmatrix ga,int i,int n,bool *visited) /從vi出發(fā)進行dfsint j; couti ; /訪問頂點vi visitedi = 1; /置訪問標志 for(j=0; jn; j+ ) /依次訪問vi的未被訪問的所有鄰接點 if(gaij != 0 & gaij != maxvalue & !visitedj) dfsmatrix(ga,j,n,visited); void bfsmatrix( adjmatr