數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)-圖的廣度優(yōu)先遍歷

學(xué)號(hào)：課程設(shè)計(jì)題目圖的廣度優(yōu)先遍歷學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)計(jì)算機(jī)科學(xué)與技術(shù)班級(jí)姓名指導(dǎo)教師2011年6月25日?qǐng)D的廣度優(yōu)先遍歷課程設(shè)計(jì)的目的課程設(shè)計(jì)是對(duì)學(xué)生的一種全面的綜合訓(xùn)練，是與課堂聽講、自學(xué)、練習(xí)、上機(jī)實(shí)習(xí)相輔相成的教學(xué)環(huán)節(jié)。課程設(shè)計(jì)的題目通常比平時(shí)練習(xí)與上機(jī)實(shí)習(xí)復(fù)雜得多，也更接近實(shí)際。其目的是使學(xué)生深化理解和靈活掌握教學(xué)內(nèi)容，并學(xué)會(huì)如何把書上學(xué)到的知識(shí)用于解決實(shí)際問題，培養(yǎng)軟件工作所需的問題分析、軟件設(shè)計(jì)、算法設(shè)計(jì)和實(shí)際動(dòng)手編程、調(diào)試的能力。這個(gè)題目的課程設(shè)計(jì)是要掌握?qǐng)D的鄰接矩陣的存儲(chǔ)結(jié)構(gòu)和圖的廣度優(yōu)先遍歷。問題分析和任務(wù)定義問題描述：畫出下圖所示的無向圖的鄰接表，使得其中每個(gè)無項(xiàng)邊結(jié)點(diǎn)中第一個(gè)頂點(diǎn)號(hào)小于第二個(gè)頂點(diǎn)號(hào)，且每個(gè)頂點(diǎn)的各鄰接邊的鏈接順序，，為它所鄰接到的頂點(diǎn)序號(hào)由小到大的順序。列出廣度優(yōu)先搜索遍歷該圖所得頂點(diǎn)序列和邊的序列。125364125364問題分析和任務(wù)定義圖的鄰接表表示：在第i行的單鏈表中，各結(jié)點(diǎn)（稱作邊結(jié)點(diǎn)）分別存放與同一個(gè)頂點(diǎn)vi關(guān)聯(lián)的各條邊。各條邊配有標(biāo)識(shí)dest，指示該邊的另一個(gè)頂點(diǎn)（終頂點(diǎn)）；還配有指針link，指向同一鏈表中的下一條邊地邊結(jié)點(diǎn)（都與頂點(diǎn)vi相關(guān)聯(lián)）。圖的遍歷:圖中某個(gè)頂點(diǎn)出發(fā)訪問圖中所有頂點(diǎn)，且使得每一頂點(diǎn)僅被訪問一次，這個(gè)過程稱為圖的遍歷。圖的遍歷是從圖中某個(gè)頂點(diǎn)出發(fā)，沿著某條搜索路徑對(duì)圖中其余每個(gè)頂點(diǎn)進(jìn)行訪問,并且使圖中的每個(gè)頂點(diǎn)僅被訪問一次的過程。存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)按無向圖的鄰接表存儲(chǔ)主要程序設(shè)計(jì)1.廣度優(yōu)先遍歷的定義在訪問了起始點(diǎn)之后,首先依次訪問起始點(diǎn)的各個(gè)鄰接點(diǎn),然后依次訪問這些頂點(diǎn)中未被訪問過的鄰接點(diǎn).依此類推,直到所有被訪問到的頂點(diǎn)的鄰接點(diǎn)都被訪問過為止.2.廣度優(yōu)先搜索的過程a算法基本思想：首先訪問圖中某一指定的出發(fā)點(diǎn)Vi；然后依次訪問Vi的所有接點(diǎn)Vi1，Vi2…Vit；再次訪問Vi1，Vi2…，Vit的鄰接點(diǎn)中未經(jīng)訪問過的頂點(diǎn)，依此類推，直到圖中所有頂點(diǎn)均被訪問為止。b具體過程：從廣度優(yōu)先搜索遍歷方法可知，先被訪問的頂點(diǎn)的鄰接點(diǎn)也被訪問，即假設(shè)頂點(diǎn)V在W之前被訪問，那么頂點(diǎn)V的所有未經(jīng)訪問的鄰接點(diǎn)也在頂點(diǎn)W的所有未經(jīng)訪問的鄰接點(diǎn)之前被訪問。這樣可以在廣度優(yōu)先遍歷的算法中設(shè)置一個(gè)隊(duì)列結(jié)構(gòu)，用以保存已訪問過的頂點(diǎn)的序號(hào)，訪問該頂點(diǎn)的所有未經(jīng)訪問的頂點(diǎn)。廣度優(yōu)先搜索是一種分層的搜索過程，每向前走一步可能訪問一批頂點(diǎn)，不像深度優(yōu)先搜索那樣會(huì)出現(xiàn)回退的現(xiàn)象。因此它不是個(gè)遞歸的過程。為了實(shí)現(xiàn)逐層訪問，算法中使用了一個(gè)隊(duì)列以記憶正在訪問的這一層和上一層的頂點(diǎn)，以便于向下一層訪問。為了避免重復(fù)訪問，需要一個(gè)輔助函數(shù)visitvex[]給被訪問過的頂點(diǎn)加標(biāo)記。調(diào)試過程1．在求圖的第u個(gè)頂點(diǎn)，與其相鄰的一系列頂點(diǎn)中，第w個(gè)頂點(diǎn)的下一個(gè)頂點(diǎn)時(shí)，若是求最后一個(gè)頂點(diǎn)的下一個(gè)頂點(diǎn)時(shí)，函數(shù)進(jìn)入了死循環(huán)。原因是判斷條件沒有寫好，造成了判斷值恒為真，因此進(jìn)入了死循環(huán)。修改后，函數(shù)正常運(yùn)行。2．廣度優(yōu)先遍歷圖的時(shí)候，是從指定的任一頂點(diǎn)開始遍歷，當(dāng)遇到該圖為無向非連通圖，并不能把該圖遍歷。原因是沒有寫出一個(gè)循環(huán)體，去嘗試遍歷其他沒有被遍歷的頂點(diǎn)。加上這樣一個(gè)循環(huán)體后，便可以遍歷任意一種圖了，并且還可以在此基礎(chǔ)上算出圖的兩通分量。3．在輸入圖信息的時(shí)候，若輸入非法字符，程序會(huì)異常終止。例如程序要求輸入一個(gè)整型，用戶卻輸入了一個(gè)字母，這時(shí)候會(huì)出現(xiàn)異常。只是程序是否健壯性的一個(gè)體現(xiàn)。采用輸入流的一些函數(shù)，便可以解決這一問題。還有其他一些類似的輸入異常，都是采用類似的處理方法。4．作為一個(gè)完整的程序，友好的界面是必須的。因次程序中適當(dāng)?shù)夭捎孟到y(tǒng)中的清屏命令，使得界面更加簡潔，明了。經(jīng)驗(yàn)與體會(huì)附源程序清單和運(yùn)行結(jié)果#include<stdio.h>#defineMaxvertex20#definemaxqueuesize20#include<stdlib.h>intvisited[Maxvertex];typedefstructnode//邊表結(jié)點(diǎn){intadjvex;//鄰接點(diǎn)域charvertex;structnode*next;//鏈域}Edgenode;typedefstructvnode//頂點(diǎn)表結(jié)點(diǎn){charvertex;//頂點(diǎn)域Edgenode*firstadj;//邊表頭指針}Vertexnode;typedefVertexnodeAdjlist[Maxvertex];//Adjlist是鄰接表類型typedefstruct{Adjlistadjlist;//鄰接表intn,e;//圖中當(dāng)前頂點(diǎn)數(shù)和邊數(shù)}ALGraph;typedefstruct{int*data;intfront;intrear;}queue;intinitqueue(queue&q){q.data=(int*)malloc(maxqueuesize*sizeof(int));q.front=q.rear=0;return1;}intisempty(queue&q){if(q.front==q.rear)return1;return0;}intisfull(queue&q){if(q.rear==maxqueuesize-1)return1;return0;}intenqueue(queue&q,inte){if(isfull(q))return0;q.data[q.rear++]=e;return1;}intdequeue(queue&q){intt;if(isempty(q))return0;//出隊(duì)t=q.data[q.front++];returnt;}voidcreatalgraph(ALGraph&G){inti,j,k;Edgenode*s;printf("輸入頂點(diǎn)數(shù)和邊數(shù)(ne):");scanf("%3d%3d",&G.n,&G.e);for(i=0;i<G.n;i++)//建立頂點(diǎn)表{printf("輸入第%d個(gè)頂點(diǎn):",i);getchar();G.adjlist[i].vertex=getchar();//讀入頂點(diǎn)信息G.adjlist[i].firstadj=NULL;}//邊表置為空表for(k=0;k<G.e;k++)//建立邊表{printf("輸入邊的頂點(diǎn)對(duì)序號(hào)(ij):");scanf("%d%d",&i,&j);//讀入邊(Vi,Vj)的頂點(diǎn)對(duì)序號(hào)s=(Edgenode*)malloc(sizeof(Edgenode));//生成邊表結(jié)點(diǎn)s->adjvex=j;//鄰接點(diǎn)序號(hào)為js->next=G.adjlist[i].firstadj;G.adjlist[i].firstadj=s;//將新結(jié)點(diǎn)*s插入頂點(diǎn)vi的邊表頭部s=(Edgenode*)malloc(sizeof(Edgenode));s->adjvex=i;//鄰接點(diǎn)序號(hào)為s->next=G.adjlist[j].firstadj;G.adjlist[j].firstadj=s;//將新結(jié)點(diǎn)*s插入頂點(diǎn)vj的邊表頭部}}intLocatevex(ALGraph&G,charv1){inti;for(i=0;i<G.n;i++){if(G.adjlist[i].vertex==v1)returni;}return0;}voidshow(ALGraph&G){inti;Edgenode*p;printf("圖的鄰接表表示如下:\n");for(i=0;i<G.n;i++){printf("[%d,%c]=>",i,G.adjlist[i].vertex);p=G.adjlist[i].firstadj;while(p!=NULL){printf("%d->",p->adjvex);p=p->next; }printf("^\n"); }}voidvisit(ALGraph&G,inti){printf("%3c",G.adjlist[i].vertex);}voidBFS(ALGraph&G,intk){inti,m;queueQ;Edgenode*p;initqueue(Q);//初始化隊(duì)列for(intj=0;j<G.n;j++)visited[j]=0;visit(G,k);visited[k]=1;enqueue(Q,k);//將訪問過的結(jié)點(diǎn)的序號(hào)入隊(duì)while(!isempty(Q)){//隊(duì)非空時(shí)出隊(duì)i=dequeue(Q);p=G.adjlist[i].firstadj;//取vi的邊表頭指針while(p){//依次搜索vi的鄰接點(diǎn)vj(令p->adjvex=j)if(!visited[p->adjvex])//若vj未訪問過{m=p->adjvex; visit(G,m);visited[m]=1;//訪問vj enqueue(Q,p->adjvex);//將訪問過的vj入隊(duì) } p=p->next;//找vi的下一鄰接點(diǎn) }}}voidmenu(){printf("**************************************\n");printf("圖的鄰接表表示\n");printf("1.創(chuàng)建圖\n");printf("2.圖的廣度優(yōu)先搜索\n");printf("3.顯示\n");printf("4.退出\n");printf("*************************************\n");}voidmain(){intk,i,j;charx,y;ALGraphG;menu();while(1){printf("\ninputyourchoice:(1~5)");scanf("%3d",&k);switch(k){case1:creatalgraph(G);break;case2:printf("inputannodestartBFS:");getchar();scanf("%c",&y);j=Locatevex(G,y);BFS(G,j);break;case3:show(G);break;case4:exit(0);break;