實(shí)驗(yàn)四圖的深度優(yōu)先與廣度優(yōu)先遍歷

1、實(shí)驗(yàn)四 圖的深度優(yōu)先與廣度優(yōu)先遍歷實(shí)驗(yàn)時(shí)間：2011年5月12日，12:50 -15:50（地點(diǎn)：7-215）實(shí)驗(yàn)?zāi)康模豪斫鈭D的邏輯特點(diǎn)；掌握理解圖的兩種主要存儲(chǔ)結(jié)構(gòu)（鄰接矩陣和鄰接表），掌握?qǐng)D的構(gòu)造、深度優(yōu)先遍歷、廣度優(yōu)先遍歷算法。具體實(shí)驗(yàn)題目：（任課教師根據(jù)實(shí)驗(yàn)大綱自己指定）每位同學(xué)按下述要求實(shí)現(xiàn)相應(yīng)算法： 根據(jù)從鍵盤輸入的數(shù)據(jù)創(chuàng)建圖（圖的存儲(chǔ)結(jié)構(gòu)可采用鄰接矩陣或鄰接表），并對(duì)圖進(jìn)行深度優(yōu)先搜索和廣度優(yōu)先搜索1）問題描述：在主程序中提供下列菜單： 1圖的建立 2深度優(yōu)先遍歷圖 3廣度優(yōu)先遍歷圖 0結(jié)束2）實(shí)驗(yàn)要求：圖的存儲(chǔ)可采用鄰接表或鄰接矩陣；定義下列過程： creategraph():

2、 按從鍵盤的數(shù)據(jù)建立圖 dfsgrahp()：深度優(yōu)先遍歷圖 bfsgrahp()：廣度優(yōu)先遍歷圖（1）算法設(shè)計(jì)思路簡介先定義鄰接矩陣和鄰接表類型，實(shí)現(xiàn)鄰接表和鄰接矩陣的相互轉(zhuǎn)換，輸出鄰接表和鄰接矩陣，再實(shí)現(xiàn)深度和廣度優(yōu)先遍歷（2）算法描述：可以用自然語言、偽代碼或流程圖等方式vertextype; /頂點(diǎn)類型mgraph; /圖的鄰接矩陣類型arcnode; /定義鄰接表類型void dispmat(mgraph g) /輸出鄰接矩陣void mattolist(mgraph g,algraph *&g) /將鄰接矩陣g轉(zhuǎn)換為鄰接表gvoid dispadj(algraph *g) /輸出鄰

3、接表void listtomat(algraph *g,mgraph g) /將鄰接表轉(zhuǎn)換為鄰接矩陣的形式void dfs(algraph *g,int v) /遞歸深度優(yōu)先遍歷void bfs(algraph *g,int v) /廣度優(yōu)先遍歷（3）算法的實(shí)現(xiàn)和測(cè)試結(jié)果：包括算法運(yùn)行時(shí)的輸入、輸出，實(shí)驗(yàn)中出現(xiàn)的問題及解決辦法等有個(gè)問題，不知如何實(shí)現(xiàn)輸入矩陣源代碼：#include#include#define max 100 /最大頂點(diǎn)個(gè)數(shù)typedef struct /以下定義臨接矩陣類型int number; /頂點(diǎn)編號(hào)int info; /頂點(diǎn)其他信息,邊的權(quán)值vertextype;

4、/頂點(diǎn)類型typedef struct /圖的定義int edgesmaxmax; /鄰接矩陣int n,e; /頂點(diǎn)數(shù)和弧數(shù) vertextype vexsmax; /存放定點(diǎn)信息mgraph; /圖的鄰接矩陣類型 /定義鄰接表類型typedef struct anode /弧的結(jié)點(diǎn)結(jié)構(gòu)類型int adjvex; /弧的重點(diǎn)位置,就是放值的struct anode *nextarc; /指向下一條弧的指針int info; /存放弧的信息（權(quán)值）arcnode;typedef struct vnode int data; /鄰接表頭結(jié)點(diǎn)的的類型arcnode *firstarc; /指向第一

5、條弧vnode;typedef vnode adjlistmax; /adjlist是鄰接表類型，把大表變成幾個(gè)小的連接到一起typedef struct adjlist adjlist; /鄰接表int n,e; /圖中頂點(diǎn)數(shù)和和邊數(shù)algraph; /圖的鄰接表類型int visitedmax; /全局?jǐn)?shù)組用于判斷后面節(jié)點(diǎn)是否被訪問過void dispmat(mgraph g) /輸出鄰接矩陣int i,j;for(i=0;ig.n;i+)for(j=0;jg.n;j+)if(g.edgesij=0)printf(0 );else printf(%d ,g.edgesij);printf(

6、n);void mattolist(mgraph g,algraph *&g) /將鄰接矩陣g轉(zhuǎn)換為鄰接表gint i,j;int n=g.n; /n為頂點(diǎn)數(shù)arcnode *p; /弧節(jié)點(diǎn)結(jié)構(gòu)的類型g=(algraph *)malloc(sizeof(algraph);for(i=0;iadjlisti.firstarc=null;for(i=0;in;i+) /檢查鄰接矩陣的每個(gè)元素for(j=0;jadjvex=j; /這是小節(jié)點(diǎn)的放值的域，只要他的列值，鏈?zhǔn)奖碇灰f明節(jié)點(diǎn)之間有關(guān)系就行，指終點(diǎn)位置p-info=g.edgesij; /存放邊的權(quán)值p-nextarc=g-adjlisti

7、.firstarc; /將*p連接到表后g-adjlisti.firstarc=p;g-e=g.e;g-n=g.n; void dispadj(algraph *g) /輸出鄰接表 int i;arcnode *p; /弧的類型for(i=0;in;i+)p=g-adjlisti.firstarc;if(p!=null)printf( %d: ,i); /這是那個(gè)大鏈表的頭while(p!=null) /順著那個(gè)頭向下查看printf( %d ,p-adjvex); /輸出弧的終點(diǎn)p=p-nextarc; printf(n);void change(int visited,algraph *g

8、) /給全局變量visited賦初值int i;for(i=0;in;i+)visitedi=0;void listtomat(algraph *g,mgraph g) /將鄰接表轉(zhuǎn)換為鄰接矩陣的形式int i,j;int n=g-n;arcnode *p;for(i=0;in;i+)for(j=0;jn;j+)g.edgesij=0;for(i=0;iadjlisti.firstarc;while(p!=null)g.edgesip-adjvex=p-info;p=p-nextarc;g.n=n;g.e=g-e;void dfs(algraph *g,int v) /遞歸深度優(yōu)先遍歷arcn

9、ode *p;/change(visited,g);visitedv=1; /第一個(gè)點(diǎn)設(shè)為已被訪問并輸出，接著以他為主進(jìn)行遍歷printf( %d,v); p=g-adjlistv.firstarc;while(p!=null)if(visitedp-adjvex=0)dfs(g,p-adjvex);p=p-nextarc; void bfs(algraph *g,int v) /廣度優(yōu)先遍歷，一個(gè)點(diǎn)先找和其有關(guān)的所有節(jié)點(diǎn)，在接著按步驟繼續(xù)arcnode *p;int queuemax,front=0,rear=0; /定義循環(huán)隊(duì)列并初始化int visitedmax;int w,i;for(

10、i=0;in;i+)visitedi=0;printf( %d ,v); /把輸入的第v個(gè)作為第一個(gè)廣度遍歷的節(jié)點(diǎn)，一直這樣進(jìn)行下去visitedv=1; rear=(rear+1)%max; /要入隊(duì)了queuerear=v; /把v入隊(duì)while(front!=rear) /隊(duì)列不為空的時(shí)候front=(front+1)%max; /要出隊(duì)了w=queuefront;p=g-adjlistw.firstarc; /跟前面差不多開始查找與頂點(diǎn)w鄰接的第一個(gè)頂點(diǎn)了while(p!=null)if(visitedp-adjvex=0) /就是當(dāng)前節(jié)點(diǎn)未被訪問printf(%d ,p-adjvex

11、);visitedp-adjvex=1;rear=(rear+1)%max; /又要入隊(duì)了，馬上要重復(fù)之前的操作了queuerear=p-adjvex;p=p-nextarc;printf(n);void main()int i,j;mgraph g;algraph *g; /沒有定義過的鄰接表類型加上*int amax6; printf(請(qǐng)輸入鄰接矩陣：n);for(i=0;i6;i+)for(j=0;j6;j+)scanf(%d,&aij);g.n=6;g.e=10;for(i=0;ig.n;i+)for(j=0;jg.n;j+)g.edgesij=aij; /這是給鄰接矩陣賦值printf(這是圖的鄰接矩陣的形式：);printf(n);dispmat(g); /輸出鄰接矩陣的函數(shù)g=(