無(wú)向圖的存儲(chǔ)及深度和廣度優(yōu)先遍歷

1、數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)題目：無(wú)序圖的存儲(chǔ)并分別實(shí)現(xiàn)深度和廣度優(yōu)先遍歷實(shí)驗(yàn)?zāi)康模豪斫獠⒄莆找脏徑颖淼姆绞酱鎯?chǔ)圖， 以及圖的非遞歸的深度和廣度優(yōu)先遍歷實(shí)驗(yàn)內(nèi)容：首先將圖的元素輸入并以鄰接表的方式存儲(chǔ)， 然后分別進(jìn)行遞歸和非遞歸遍歷。一、需求分析1、輸入的形式和輸入值的范圍：輸入圖的頂點(diǎn)元素和邊；輸入數(shù)字選擇要進(jìn)行的操作：深度遍歷，廣度遍歷或結(jié)束操作。2、輸出的形式：按深度或者廣度優(yōu)先順序輸出各節(jié)點(diǎn)的編號(hào)3、程序所能達(dá)到的功能：(1)以鄰接表的方式存儲(chǔ)圖(2)對(duì)圖進(jìn)行深度優(yōu)先的非遞歸遍歷(3)對(duì)圖進(jìn)行廣度優(yōu)先的非遞歸遍歷4、測(cè)試數(shù)據(jù)：輸入各結(jié)點(diǎn)元素：a,b,c,d,e,f,g,h ；輸入圖中的各邊：1

2、,2 1,3 2,4 2,5 3,6 3,7 4,8 5,8操作選項(xiàng) 輸入1進(jìn)行深度優(yōu)先遍歷；遍歷結(jié)果為：1 3 7 6 2 5 8 4操作選項(xiàng) 輸入2進(jìn)行廣度優(yōu)先遍歷；遍歷結(jié)果為：1 3 2 7 6 5 4二概要設(shè)計(jì)(1)抽象數(shù)據(jù)類型定義:#define MaxVerNum 100/邊表結(jié)點(diǎn)typedef struct node int adjvex;struct node *next;EdgeNode,*ENode;頂點(diǎn)表結(jié)點(diǎn)；typedef struct vnodechar vertex;EdgeNode *firstedge;VertexNode;typedef VertexNode

3、AdjListMaxVerNum;定義圖；typedef structAdjList adjlist;int n,e;AlGraph;AlGraph G;(2)主程序的流程：1 .根據(jù)提示輸入頂點(diǎn)個(gè)數(shù)和邊的個(gè)數(shù);2 .輸入圖的各邊；3 .輸入數(shù)字執(zhí)行相關(guān)操作(3)其函數(shù)之間調(diào)用關(guān)系如下：main()執(zhí)行結(jié)束后，重新執(zhí)行判定操作和循環(huán)三詳細(xì)設(shè)計(jì)1 .元素類型#define MaxVerNum 100typedef struct nodeint adjvex;struct node *next;EdgeNode,*ENode;typedef struct vnodechar vertex;Edge

4、Node *firstedge;VertexNode;typedef VertexNode AdjListMaxVerNum;typedef structAdjList adjlist;int n,e;AlGraph;AlGraph G;2 .每個(gè)模塊的分析：(1)主程序模塊：int main()int a,v;/創(chuàng)建圖Create(G);printf("請(qǐng)選擇要進(jìn)行的操作：n選擇深度優(yōu)先請(qǐng)輸入1; n選擇廣度優(yōu)先請(qǐng)輸入2； n結(jié)束操作請(qǐng)輸入0n");scanf("%d",&a);while(a!=0)printf("請(qǐng)輸入開(kāi)始遍歷頂點(diǎn)

5、的坐標(biāo)n");scanf("%d",&v);if(a=1)/深度優(yōu)先遍歷DfsTravel(G,v);else if(a=2)/廣度優(yōu)先遍歷 BfsTravel(G,v);printf("請(qǐng)選擇要進(jìn)行的操作：n選擇深度優(yōu)先請(qǐng)輸入1; n選擇廣度優(yōu)先請(qǐng)輸入2； n結(jié)束操作請(qǐng)輸入0n");scanf("%d",&a);return 0;)(2)深度優(yōu)先遍歷void DfsTravel(AlGraph &G,int v)(ENode stackMaxVerNum;ENode p;int visitedMax

6、VerNum,top=-1,i;for(i=0;i<G.n;i+)visitedi=0;printf("深度優(yōu)先遍歷的結(jié)果為：n");printf("%d ",v);visitedv=1;p=G.adjlistv.firstedge;while(top!=-1|p!=NULL)(while(p!=NULL)(if(visitedp->adjvex=1) p=p->next;else(printf("%d ”,p->adjvex);visitedp->adjvex=1;top+;stacktop=p;p=G.adjl

7、istp->adjvex.firstedge;)if(top!=-1) p=stacktop;top-;p=p->next;)printf("n");)(3)廣度優(yōu)先遍歷void BfsTravel(AlGraph &G,int v)int visitedMaxVerNum;int queueMaxVerNum;int front=-1,rear=-1;EdgeNode *p;int i;for(i=0;i<G.n;i+)visitedi=0;printf("廣度優(yōu)先遍歷的結(jié)果為：n");printf("%d &quo

8、t;,v);visitedv=1;rear=rear+1;queuerear=v;while(front!=rear)(front+;v=queuefront;p=G.adjlistv.firstedge;while(p!=NULL)(if(visitedp->adjvex=0)printf("%d ",p->adjvex);visitedp->adjvex=1;rear=rear+1;queuerear=p->adjvex;)p=p->next;)printf("n");)創(chuàng)建圖void Create(AlGraph &a

9、mp;G)int i,j,k;EdgeNode *s,*r;printf("請(qǐng)依次輸入無(wú)向圖頂點(diǎn)個(gè)數(shù)和邊的個(gè)數(shù)n");scanf("%d,%d",&(G.n),&(G.e);getchar();printf("請(qǐng)輸入各頂點(diǎn)信息n");for(i=0;i<G.n;i+)scanf("%c",&(G.adjlisti.vertex);getchar();G.adjlistifirstedge=NULL;)printf("請(qǐng)輸入各邊的信息，輸入格式為i,jn");for(

10、k=0;k<G.e;k+)scanf("%d,%d",&i,&j);s=(EdgeNode*)malloc(sizeof(EdgeNode);s->adjvex=j;s->next= G.adjlisti.firstedge;G.adjlisti.firstedge=s;r=(EdgeNode*)malloc(sizeof(EdgeNode);r->adjvex=i;r->next= G.adjlistj.firstedge;G.adjlistj.firstedge=r;)四 使用說(shuō)明、測(cè)試分析及結(jié)果輸入各結(jié)點(diǎn)元素：a,b,c,

11、d,e,f,g,h ；輸入圖中的各邊：1,2 1,3 2,4 2,5 3,6 3,7 4,8 5,8操作選項(xiàng) 輸入1進(jìn)行深度優(yōu)先遍歷；遍歷結(jié)果為：1 3 7 6 2 5 8 4操作選項(xiàng) 輸入2進(jìn)行廣度優(yōu)先遍歷；遍歷結(jié)果為：1 3 2 7 6 5 41.程序使用說(shuō)明；(1)本程序的運(yùn)行環(huán)境為 VC6.0。(2)進(jìn)入演示程序后即顯示提示信息：請(qǐng)輸入頂點(diǎn)個(gè)數(shù)和邊的個(gè)數(shù)：2、測(cè)試結(jié)果與分析；輸入各結(jié)點(diǎn)元素：a,b,c,d,e,f,g,h ；輸入圖中的各邊：1,2 1,3 2,4 2,5 3,6 3,7 4,8 5,8操作選項(xiàng) 輸入1進(jìn)行深度優(yōu)先遍歷；遍歷結(jié)果為：1 3 7 6 2 5 8 4操作選項(xiàng) 輸入2進(jìn)行廣度優(yōu)先遍歷；遍歷結(jié)果為：1 3 2 7 6 5 43、運(yùn)行界面。請(qǐng)依次輸入無(wú)向圖頂點(diǎn)個(gè)數(shù)和邊的個(gè)數(shù)8 8宿輸入各頂點(diǎn)信息營(yíng)凈房.日濰，千次g.h請(qǐng)輸入各邊的信息，輸入格式為i,j1,32,42,53,63.7*85,8請(qǐng)選擇要進(jìn)行的操