天津理工大學(xué)數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告4

計(jì)算機(jī)科學(xué)與工程系PAGEPAGE9計(jì)算機(jī)科學(xué)與工程系實(shí)驗(yàn)（四）實(shí)驗(yàn)名稱圖的深度優(yōu)先與廣度優(yōu)先遍歷軟件環(huán)境Windows98/2000,VC++6.0或turboC硬件環(huán)境PⅡ以上微型計(jì)算機(jī)實(shí)驗(yàn)?zāi)康睦斫鈭D的邏輯特點(diǎn)，理解圖的鄰接矩陣或鄰接表存儲(chǔ)結(jié)構(gòu)，掌握?qǐng)D的深度優(yōu)先遍歷、廣度優(yōu)先遍歷算法。實(shí)驗(yàn)內(nèi)容（應(yīng)包括實(shí)驗(yàn)題目、實(shí)驗(yàn)要求、實(shí)驗(yàn)任務(wù)等）圖的遍歷利用鄰接矩陣或鄰接表作為存儲(chǔ)結(jié)構(gòu)建立一個(gè)無向圖，每個(gè)頂點(diǎn)中存放一種水果名(例如apple、orange、banana等，并要求從鍵盤輸入)，頂點(diǎn)數(shù)不少于5個(gè)。要求分別以深度優(yōu)先搜索(DFS)和廣度優(yōu)先搜索(BFS)進(jìn)行遍歷，輸出遍歷結(jié)果。實(shí)驗(yàn)過程與實(shí)驗(yàn)結(jié)果（可包括實(shí)驗(yàn)實(shí)施的步驟、算法描述、流程、結(jié)論等）實(shí)驗(yàn)步驟及算法描述和流程：無向圖的鄰接矩陣存儲(chǔ)結(jié)構(gòu)創(chuàng)建無向圖的邊的結(jié)構(gòu)，由該邊的信息指針和組成該邊的兩個(gè)頂點(diǎn)的位置以及指向與兩個(gè)頂點(diǎn)相連的下一條邊構(gòu)成創(chuàng)建無向圖的頂點(diǎn)結(jié)構(gòu)，由頂點(diǎn)所存儲(chǔ)的信息和指向依附該頂點(diǎn)的邊的指針構(gòu)成創(chuàng)建無向圖的結(jié)構(gòu)，由頂點(diǎn)結(jié)構(gòu)數(shù)組和無向圖當(dāng)前的頂點(diǎn)數(shù)和邊數(shù)構(gòu)成利用單鏈隊(duì)列作為無向圖的鄰接表存儲(chǔ)結(jié)構(gòu)采用鄰接表存儲(chǔ)結(jié)構(gòu)，構(gòu)造無向圖輸入無向圖的相關(guān)信息：頂點(diǎn)數(shù)，邊數(shù)，再輸入頂點(diǎn)信息構(gòu)造表節(jié)點(diǎn)鏈表輸入頂點(diǎn)間的關(guān)系，構(gòu)造出無向圖的鄰接表深度優(yōu)先遍歷無向圖編寫函數(shù)DFS，從頂點(diǎn)v出發(fā)，對(duì)v所在的連通分量進(jìn)行深度優(yōu)先搜索，并利用遞歸，輸出結(jié)點(diǎn)信息并對(duì)未訪問的結(jié)點(diǎn)調(diào)用DFS函數(shù)3.2編寫函數(shù)DFSTraverse對(duì)無向圖做深度優(yōu)先搜索，對(duì)已訪問的結(jié)點(diǎn)標(biāo)記，對(duì)尚未訪問過得結(jié)點(diǎn)調(diào)用DFS廣度優(yōu)先遍歷無向圖使用輔助隊(duì)列Q和訪問標(biāo)志數(shù)組visite對(duì)無向圖進(jìn)行非遞歸廣度優(yōu)先搜索用for循環(huán)給頂點(diǎn)訪問標(biāo)志數(shù)組置初值0若頂點(diǎn)未訪問對(duì)要訪問頂點(diǎn)訪問標(biāo)志置為1，頂點(diǎn)入隊(duì)循環(huán)當(dāng)隊(duì)列不為空時(shí)，隊(duì)頭元素出隊(duì)賦給u，并將u的未訪問的鄰接點(diǎn)入隊(duì)主函數(shù)調(diào)用無向圖創(chuàng)建函數(shù)從鍵盤輸入數(shù)據(jù)創(chuàng)建無向圖調(diào)用深度優(yōu)先函數(shù)，輸出無向圖的深度優(yōu)先搜索調(diào)用廣度優(yōu)先函數(shù)，輸出無向圖的廣度優(yōu)先搜索結(jié)論：因?yàn)槌绦蛑朽徑颖淼某鋈霝轭^插法，所以對(duì)于輸入無向圖的關(guān)系時(shí)，鄰接表的生成總與輸入時(shí)的順序相反，在做深度與廣度優(yōu)先搜索時(shí)，對(duì)于結(jié)點(diǎn)a，首先訪問的結(jié)點(diǎn)，是輸入邊的關(guān)系時(shí)最后輸入的附錄（可包括源程序清單或其它說明）#include<stdio.h>#include<string>#defineMAX_NAME10#defineMAX_INFO80typedefcharInfoType;typedefcharVertexType[MAX_NAME];//字符串類型#defineMAX_VERTEX_NUM20typedefenum{unvisited,visited}VisitIf;typedefstructEBox{ VisitIfmark;//訪問標(biāo)記 intivex,jvex;//該邊依附的兩個(gè)頂點(diǎn)的位置 structEBox*ilink,*jlink;//分別指向依附這兩個(gè)頂點(diǎn)的下一條邊 InfoType*info;//該邊信息指針}EBox;typedefstruct{ VertexTypedata; EBox*firstedge;//指向第一條依附該頂點(diǎn)的邊}VexBox;typedefstruct{ VexBoxadjmulist[MAX_VERTEX_NUM]; intvexnum,edgenum;//無向圖的當(dāng)前頂點(diǎn)數(shù)和邊數(shù)}AMLGraph;typedefintQElemType;typedefstructQNode{//單鏈表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) QElemTypedata; //數(shù)據(jù)域 structQNode*next; //指針域}QNode,*QueuePtr;typedefstruct{ QueuePtrfront,//隊(duì)頭指針，指針域指向隊(duì)頭元素 rear;//隊(duì)尾指針，指向隊(duì)尾元素}LinkQueue;//若G中存在頂點(diǎn)u,則返回該頂點(diǎn)在無向圖中位置;否則返回-1intLocateVex(AMLGraphG,VertexTypeu){ inti; for(i=0;i<G.vexnum;++i) if(strcmp(u,G.adjmulist[i].data)==0) returni; return-1;}intCreateGraph(AMLGraph*G){//采用鄰接表存儲(chǔ)結(jié)構(gòu),構(gòu)造無向圖G inti,j,k,l,IncInfo; chars[MAX_INFO]; VertexTypeva,vb; EBox*p; printf("請(qǐng)輸入無向圖G的頂點(diǎn)數(shù),邊數(shù):"); scanf("%d,%d",&(*G).vexnum,&(*G).edgenum); printf("請(qǐng)輸入%d個(gè)頂點(diǎn)的值(<%d個(gè)字符):\n",(*G).vexnum,MAX_NAME); for(i=0;i<(*G).vexnum;++i){//構(gòu)造頂點(diǎn)向量 scanf("%s",(*G).adjmulist[i].data); (*G).adjmulist[i].firstedge=NULL; } printf("請(qǐng)順序輸入每條邊的兩個(gè)端點(diǎn)(以空格作為間隔):\n"); for(k=0;k<(*G).edgenum;++k){//構(gòu)造表結(jié)點(diǎn)鏈表 scanf("%s%s%*c",va,vb);//%*c吃掉回車符 i=LocateVex(*G,va);//一端 j=LocateVex(*G,vb);//另一端 p=(EBox*)malloc(sizeof(EBox)); p->mark=unvisited;//設(shè)初值 p->ivex=i; p->jvex=j; p->info=NULL; p->ilink=(*G).adjmulist[i].firstedge;//插在表頭 (*G).adjmulist[i].firstedge=p; p->jlink=(*G).adjmulist[j].firstedge;//插在表頭 (*G).adjmulist[j].firstedge=p; } return1;}VertexType*GetVex(AMLGraphG,intv){//返回v的值 if(v>=G.vexnum||v<0) exit(0); return&G.adjmulist[v].data;}//返回v的第一個(gè)鄰接頂點(diǎn)的序號(hào)。若頂點(diǎn)在G中沒有鄰接頂點(diǎn),則返回-1intFirstAdjVex(AMLGraphG,VertexTypev){ inti; i=LocateVex(G,v); if(i<0) return-1; if(G.adjmulist[i].firstedge)//v有鄰接頂點(diǎn) if(G.adjmulist[i].firstedge->ivex==i) returnG.adjmulist[i].firstedge->jvex; else returnG.adjmulist[i].firstedge->ivex; else return-1;}//返回v的(相對(duì)于w的)下一個(gè)鄰接頂點(diǎn)的序號(hào)。若w是v的最后一個(gè)鄰接點(diǎn),則返回-1intNextAdjVex(AMLGraphG,VertexTypev,VertexTypew){ inti,j; EBox*p; i=LocateVex(G,v);//i是頂點(diǎn)v的序號(hào) j=LocateVex(G,w);//j是頂點(diǎn)w的序號(hào) if(i<0||j<0)//v或w不是G的頂點(diǎn) return-1; p=G.adjmulist[i].firstedge;//p指向頂點(diǎn)v的第1條邊 while(p) if(p->ivex==i&&p->jvex!=j)//不是鄰接頂點(diǎn)w(情況1) p=p->ilink;//找下一個(gè)鄰接頂點(diǎn) elseif(p->jvex==i&&p->ivex!=j)//不是鄰接頂點(diǎn)w(情況2) p=p->jlink;//找下一個(gè)鄰接頂點(diǎn) else//是鄰接頂點(diǎn)w break; if(p&&p->ivex==i&&p->jvex==j){//找到鄰接頂點(diǎn)w(情況1) p=p->ilink; if(p&&p->ivex==i) returnp->jvex; elseif(p&&p->jvex==i) returnp->ivex; } if(p&&p->ivex==j&&p->jvex==i){//找到鄰接頂點(diǎn)w(情況2) p=p->jlink; if(p&&p->ivex==i) returnp->jvex; elseif(p&&p->jvex==i) returnp->ivex; } return-1;}intvisite[MAX_VERTEX_NUM];//訪問標(biāo)志數(shù)組(全局量)int(*VisitFunc)(VertexTypev);voidDFS(AMLGraphG,intv){ intj; EBox*p; VisitFunc(G.adjmulist[v].data); visite[v]=1; p=G.adjmulist[v].firstedge; while(p){ j=p->ivex==v?p->jvex:p->ivex; if(!visite[j]) DFS(G,j); p=p->ivex==v?p->ilink:p->jlink; }}//從第1個(gè)頂點(diǎn)起,深度優(yōu)先遍歷圖G,并對(duì)每個(gè)頂點(diǎn)調(diào)用函數(shù)VisitvoidDFSTraverse(AMLGraphG,int(*visit)(VertexType)){ intv; VisitFunc=visit; for(v=0;v<G.vexnum;v++) visite[v]=0; for(v=0;v<G.vexnum;v++) if(!visite[v]) DFS(G,v); printf("\n");}intInitQueue(LinkQueue*Q){//構(gòu)造一個(gè)空隊(duì)列Q (*Q).front=(*Q).rear=(QueuePtr)malloc(sizeof(QNode)); //動(dòng)態(tài)分配一個(gè)空間 if(!(*Q).front) exit(0); (*Q).front->next=NULL; //隊(duì)頭指針指向空，無數(shù)據(jù)域，這樣構(gòu)成了一個(gè)空隊(duì)列 return1;}intQueueEmpty(LinkQueueQ){//若Q為空隊(duì)列,則返回1,否則返回0 if(Q.front==Q.rear) return1; else return0;}intEnQueue(LinkQueue*Q,QElemTypee){//插入元素e為Q的新的隊(duì)尾元素 QueuePtrp=(QueuePtr)malloc(sizeof(QNode)); if(!p)//存儲(chǔ)分配失敗 exit(0); //生成一個(gè)以為e為數(shù)據(jù)域的隊(duì)列元素 p->data=e; p->next=NULL; //將該新隊(duì)列元素接在隊(duì)尾的后面 (*Q).rear->next=p; (*Q).rear=p; return1;}//若隊(duì)列不空,刪除Q的隊(duì)頭元素,用e返回其值,并返回1,否則返回0intDeQueue(LinkQueue*Q,QElemType*e){ QueuePtrp; if((*Q).front==(*Q).rear) return0; p=(*Q).front->next; //隊(duì)頭元素 *e=p->data; (*Q).front->next=p->next; if((*Q).rear==p) (*Q).rear=(*Q).front; free(p); return1;}//從第1個(gè)頂點(diǎn)起,按廣度優(yōu)先非遞歸遍歷圖G,并對(duì)每個(gè)頂點(diǎn)調(diào)用函數(shù)//Visit一次且僅一次。使用輔助隊(duì)列Q和訪問標(biāo)志數(shù)組visitevoidBFSTraverse(AMLGraphG,int(*Visit)(VertexType)){ intv,u,w; VertexTypew1,u1; LinkQueueQ; for(v=0;v<G.vexnum;v++) visite[v]=0;//置初值 InitQueue(&Q);//置空的輔助隊(duì)列Q for(v=0;v<G.vexnum;v++) if(!visite[v]){//v尚未訪問 visite[v]=1;//設(shè)置訪問標(biāo)志為1(已訪問) Visit(G.adjmulist[v].data); EnQueue(&Q,v);//v入隊(duì)列 while(!QueueEmpty(Q)){//隊(duì)列不空 DeQueue(&Q,&u);//隊(duì)頭元素出隊(duì)并置為u strcpy(u1,*GetVex(G,u))