實(shí)驗(yàn)報(bào)告：圖的存儲(chǔ)結(jié)構(gòu)和遍歷

1、-. z.*東湖學(xué)院實(shí) 驗(yàn) 報(bào) 告學(xué)院：計(jì)算機(jī)科學(xué)學(xué)院專業(yè)計(jì)算機(jī)科學(xué)與技術(shù)2016年 11月18日姓 名付磊學(xué) 號(hào)42班 級(jí)計(jì)科一班指導(dǎo)教師吳佳芬課程名稱數(shù)據(jù)構(gòu)造成績(jī)實(shí)驗(yàn)名稱圖的存儲(chǔ)構(gòu)造和遍歷1實(shí)驗(yàn)?zāi)康?了解鄰接矩陣存儲(chǔ)法和鄰接表存儲(chǔ)法的實(shí)現(xiàn)過程。2了解圖的深度優(yōu)先遍歷和廣度優(yōu)先遍歷的實(shí)現(xiàn)過程。2實(shí)驗(yàn)內(nèi)容1. 采用圖的鄰接矩陣存儲(chǔ)方法，實(shí)現(xiàn)下列圖的鄰接矩陣存儲(chǔ)，并輸出該矩陣.2. 設(shè)計(jì)一個(gè)將第1小題中的鄰接矩陣轉(zhuǎn)換為鄰接表的算法，并設(shè)計(jì)一個(gè)在屏幕上顯示鄰接表的算法3. 實(shí)現(xiàn)基于第2小題中鄰接表的深度優(yōu)先遍歷算法，并輸出遍歷序列4. 實(shí)現(xiàn)基于第2小題中鄰接表的廣度優(yōu)先遍歷算法，并輸出遍歷序列3實(shí)

2、驗(yàn)環(huán)境Visual C+ 6.04實(shí)驗(yàn)方法和步驟含設(shè)計(jì)我們通過二維數(shù)組中的值來表示圖中節(jié)點(diǎn)與節(jié)點(diǎn)的關(guān)系。通過上圖可知，其鄰接矩陣示意圖為如下：V0 v1 v2 v3 v4 v5V00 1 0 1 0 1V1 1 0 1 1 1 0V2 0 1 0 0 1 0V3 1 1 0 0 1 1V4 0 1 1 1 0 0V5 1 0 0 1 0 0此時(shí)的1表示這兩個(gè)節(jié)點(diǎn)有關(guān)系，0表示這兩個(gè)節(jié)點(diǎn)無關(guān)系。 我們通過鄰接表來在計(jì)算機(jī)中存儲(chǔ)圖時(shí)，其鄰接表存儲(chǔ)圖如下：5程序及測(cè)試結(jié)果# include # include int visited 6;typedef struct int a66; int n;m

3、graph;typedef struct ANode int adjve*;struct ANode *ne*tarc;Arode;typedef struct Vnode Arode *firstarc;VNode;typedef VNode AdjList6;typedef struct AdjList adjlist; int n;ALGraph;void mattolist (mgraph g,ALGraph *&G) int i,j; Arode *p; G=(ALGraph*)malloc(sizeof(ALGraph); for(i=0;iadjlisti.firstarc=NU

4、LL; for(i=0;i=0;j-) if(g.aij!=0) p=(Arode*)malloc(sizeof(Arode); p-adjve*=j; p-ne*tarc=G-adjlisti.firstarc; G-adjlisti.firstarc=p; G-n=g.n;void dispadj(ALGraph *G) int i; Arode *p;for(i=0;in;i+) p=G-adjlisti.firstarc; printf(%d:,i); while (p!=NULL) printf(%d ,p-adjve*); p=p-ne*tarc; printf(n);void d

5、fs (ALGraph *G,int v)Arode *p;visited v=1;printf(%d ,v);p=G-adjlistv.firstarc;while (p!=NULL) if(visitedp-adjve*=0) dfs(G,p-adjve*); p=p-ne*tarc; void bfs (ALGraph *G ,int v) Arode *p; int queue6,front=0,rear=0; int visited6; int w,i; for(i=0;in;i+) visitedi=0; printf(%d ,v); visitedv=1; rear=(rear+

6、1)%6; queuerear=v; while (front!=rear) front=(front+1)%6; w=queuefront; p=G-adjlistw.firstarc; while(p!=NULL) if(visitedp-adjve*=0) printf(%d ,p-adjve*); visitedp-adjve*=1; rear=(rear+1)%6; queuerear=p-adjve*; p=p-ne*tarc; printf(n);int main ()mgraph g;ALGraph *G;int a66=0,1,0,1,0,1,1,0,1,1,1,0,0,1,

7、0,0,1,0,1,1,0,0,1,1,0,1,1,1,0,0,1,0,0,1,0,0;int i,j;g.n=6;for(i=0;ig.n;i+)for(j=0;jg.n;j+)g.aij=aij;for(i=0;ig.n;i+)for(j=0;jg.n;j+)printf(%d ,g.aij);printf(n);printf(-鄰接矩陣-n);G=(ALGraph*)malloc(sizeof(ALGraph);mattolist(g,G);dispadj(G);printf(-鄰接表-n);dfs(G,0);printf(n);printf(-從0開場(chǎng)的深度優(yōu)先遍歷-n); bfs(G,0); printf(n);printf(-從0開場(chǎng)的廣度優(yōu)先遍歷-n);return 0;6實(shí)驗(yàn)分析與體會(huì)通過此次實(shí)驗(yàn)，使我更加深刻的明白了圖在計(jì)算機(jī)中是如何存儲(chǔ)的，圖在計(jì)算機(jī)中的存儲(chǔ)有兩種，一種是鄰接矩陣存儲(chǔ)方式，這種方式我們主要是運(yùn)用到了二維數(shù)組的特性，通過二維數(shù)組來明確表現(xiàn)出節(jié)點(diǎn)與節(jié)點(diǎn)的位置關(guān)系，第二種就是我們說的鄰接表存儲(chǔ)構(gòu)造，這種構(gòu)造主要是運(yùn)用到了指針來實(shí)現(xiàn)。而當(dāng)我們?cè)谶M(jìn)展圖的遍歷時(shí)，首先要選擇一個(gè)起始點(diǎn)，上面我們選擇的是0為起始點(diǎn)，當(dāng)我們?cè)谶M(jìn)展深度優(yōu)先遍歷時(shí)，可以用遞歸的思想，而在廣度優(yōu)先遍歷時(shí)，不能用遞歸，這個(gè)要注意。在這次的實(shí)驗(yàn)中，通過對(duì)圖的操作，使我對(duì)