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

上傳人：奔*** IP屬地：河北更新時間：2024-03-01 格式：docx 頁數(shù)：13 大?。?50.74KB 人氣指數(shù)：12 舉報 版權(quán)申訴

已閱讀1頁，還剩12頁未讀，繼續(xù)免費(fèi)閱讀

版權(quán)說明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權(quán)，請進(jìn)行舉報或認(rèn)領(lǐng)

文檔簡介

1、　　課程設(shè) 計　　課程設(shè)計任務(wù)書　　題目: 圖的廣度優(yōu)先遍歷 　　初始條件：

2、　　（1）采用鄰接表作為存儲結(jié)構(gòu)；　?。?）指定任一頂點(diǎn)作為出發(fā)點(diǎn)進(jìn)行廣度優(yōu)先遍歷；　?。?）測試用例見嚴(yán)蔚敏《數(shù)據(jù)結(jié)構(gòu)習(xí)題集(C語言版)》p47題7.3圖　　要求完成的主要任務(wù): （包括課程設(shè)計工作量及其技術(shù)要求，以及說明書撰寫等具體要求）　　課程設(shè)計

3、報告按學(xué)校規(guī)定格式用A4紙打印（書寫），并應(yīng)包含如下內(nèi)容： 　　1. 問題描述　　簡述題目要解決的問題是什么。　　2. 設(shè)計　　存儲結(jié)構(gòu)設(shè)計、主要算法設(shè)計（用類C/C++語言或用框圖描述）、測試用

4、例設(shè)計；　　3. 調(diào)試報告　　調(diào)試過程中遇到的問題是如何解決的；對設(shè)計和編碼的討論和分析。　　4. 經(jīng)驗和體會（包括對算法改進(jìn)的設(shè)想）　　5. 附源程序清單和運(yùn)行結(jié)果。源程序要加注釋。如果題目規(guī)定了測試數(shù)據(jù)，則運(yùn)行結(jié)果要包含這些測試數(shù)

5、據(jù)和運(yùn)行輸出。　　說明：　　1. 設(shè)計報告、程序不得相互抄襲和拷貝；若有雷同，則所有雷同者成績均為0分。　　2. 凡拷貝往年任務(wù)書或課程設(shè)計充數(shù)者，成績一律無效，以0分記。　　時間安排：</

6、p>　　1、第19周完成。　　2、6月30日下午-7月1日在實(shí)驗中心檢查程序、交課程設(shè)計報告、源程序（U盤）。　　指導(dǎo)教師簽名：年月日　　系主任（或責(zé)任教師）簽名：年月

7、日　　圖的廣度優(yōu)先遍歷　　課程設(shè)計的目的　　課程設(shè)計是對學(xué)生的一種全面的綜合訓(xùn)練，是與課堂聽講、自學(xué)、練習(xí)、上機(jī)實(shí)習(xí)相輔相成的教學(xué)環(huán)節(jié)。課程設(shè)計的題目通常比平時練習(xí)與上機(jī)實(shí)習(xí)復(fù)雜得多，也更接近實(shí)際。其目的是使學(xué)生深化理解和靈活掌握

8、教學(xué)內(nèi)容，并學(xué)會如何把書上學(xué)到的知識用于解決實(shí)際問題，培養(yǎng)軟件工作所需的問題分析、軟件設(shè)計、算法設(shè)計和實(shí)際動手編程、調(diào)試的能力。　　這個題目的課程設(shè)計是要掌握圖的鄰接矩陣的存儲結(jié)構(gòu)和圖的廣度優(yōu)先遍歷。　　問題分析和任務(wù)定義　　2.1問題描述：</b&g

9、t;　　畫出下圖所示的無向圖的鄰接表，使得其中每個無項邊結(jié)點(diǎn)中第一個頂點(diǎn)號小于第二個頂點(diǎn)號，且每個頂點(diǎn)的各鄰接邊的鏈接順序，，為它所鄰接到的頂點(diǎn)序號由小到大的順序。列出廣度優(yōu)先搜索遍歷該圖所得頂點(diǎn)序列和邊的序列。　　2.2問題分析和任務(wù)定義　　圖的鄰接表表示：在第i行的單鏈表中，各結(jié)點(diǎn)（稱作邊結(jié)點(diǎn)）分別存放與同一

10、個頂點(diǎn)vi關(guān)聯(lián)的各條邊。各條邊配有標(biāo)識dest，指示該邊的另一個頂點(diǎn)（終頂點(diǎn)）；還配有指針link，指向同一鏈表中的下一條邊地邊結(jié)點(diǎn)（都與頂點(diǎn)vi相關(guān)聯(lián)）。 　　圖的遍歷: 圖中某個頂點(diǎn)出發(fā)訪問圖中所有頂點(diǎn)，且使得每一頂點(diǎn)僅被訪問一次，這個過程稱為圖的遍歷。圖的遍歷是從圖中某個頂點(diǎn)出發(fā)，沿著某條搜索路徑對圖中其余每個頂點(diǎn)進(jìn)行訪問, 并且使圖中的每個頂點(diǎn)僅被訪問一次的過程。

11、　　存儲結(jié)構(gòu)設(shè)計　　按無向圖的鄰接表存儲　　主要程序設(shè)計　　4.1.廣度優(yōu)先遍歷的定義　　在訪問了起始點(diǎn)之后,首先依次訪問起始點(diǎn)的各個鄰接點(diǎn),然后依次訪問這些頂點(diǎn)中未被訪問過的

12、鄰接點(diǎn).依此類推,直到所有被訪問到的頂點(diǎn)的鄰接點(diǎn)都被訪問過為止.　　4.2 廣度優(yōu)先搜索的過程　　4.2.1算法基本思想：　　首先訪問圖中某一指定的出發(fā)點(diǎn)Vi；　　然后依次訪問Vi的所有接點(diǎn)Vi1，Vi2…Vit；　　再次訪問Vi

13、1，Vi2…，Vit的鄰接點(diǎn)中未經(jīng)訪問過的頂點(diǎn)，依此類推，直到圖中所有頂點(diǎn)均被訪問為止。　　4.2.2具體過程：　　從廣度優(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è)置一個隊列結(jié)構(gòu)，用以保存已訪問過的頂點(diǎn)的序號

14、，訪問該頂點(diǎn)的所有未經(jīng)訪問的頂點(diǎn)。　　廣度優(yōu)先搜索是一種分層的搜索過程，每向前走一步可能訪問一批頂點(diǎn)，不像深度優(yōu)先搜索那樣會出現(xiàn)回退的現(xiàn)象。因此它不是個遞歸的過程。為了實(shí)現(xiàn)逐層訪問，算法中使用了一個隊列以記憶正在訪問的這一層和上一層的頂點(diǎn)，以便于向下一層訪問。為了避免重復(fù)訪問，需要一個輔助函數(shù)visitvex[]給被訪問過的頂點(diǎn)加標(biāo)記。 　　4.3圖的廣

15、度優(yōu)先遍歷流程圖　　是　　否　　否　　是　　4.4廣度優(yōu)先遍歷的偽代碼<

16、/p>　　#include<iostream.h>　　Struct edgenode{}//定義邊的結(jié)構(gòu)體　　Struct vexnode{}//定義頂點(diǎn)的結(jié)構(gòu)體　　Struct Graph{}//定義圖的結(jié)構(gòu)體　　//隊列的定義及

17、相關(guān)函數(shù)的實(shí)現(xiàn)　　Struct QueueNode{}//定義隊列結(jié)點(diǎn)的結(jié)構(gòu)體　　struct QueueList 　　{//定義隊列的頭指針和尾指針，為用鏈表的形式構(gòu)建隊列　　};　　voi

18、d EnQueue(QueueList* Q,int e)//定義隊列的進(jìn)站操作　　{ QueueNode *q=new QueueNode;//建立新的結(jié)點(diǎn)，并作賦值操作　　if(Q==NULL)//返回　　if(Q->rear==NULL//是隊列的頭指針和尾指針都指向q<

19、;p>　　else　　{//將尾指針的連接到q上，在使尾指針指向向一個節(jié)點(diǎn)}　　}　　void DeQueue(QueueList* Q,int* e)//實(shí)現(xiàn)隊列的進(jìn)站操作　　{if (Q

20、==NULL)//返回　　if (Q->front==Q->rear){　　*e=Q->front->nData;Q->front=Q->rear=NULL;}　　else{*e=Q->front->nData;Q->front=Q->front-&g

21、t;next;}}　　//創(chuàng)建圖　　void CreatAdjList(Graph* G){　　輸入頂點(diǎn)數(shù)和邊數(shù)　　輸入頂點(diǎn)表<

22、p>　　for (i=0;i<G->vexnum;i++)　　{建立頂點(diǎn)表　　}　　輸入邊表的信息　　for (k=0;k<G->

23、;arcnum;k++)　　{　　請輸入邊<Vi,Vj>對應(yīng)的頂點(diǎn)　　//因為是無向圖，所以有兩次建立邊表的過程　　}

24、　}　　//廣度優(yōu)先遍歷　　void BFS(Graph* G,int v,int visit[])　　初始化隊列　　EnQueue(Q,v);//頂點(diǎn)進(jìn)站實(shí)行分層訪問&l

25、t;/p>　　//循環(huán)，訪問所有結(jié)點(diǎn)　　//從隊列中推出頂點(diǎn)　　//找到頂點(diǎn)的第一個鄰接頂點(diǎn)，若鄰接頂點(diǎn)存在進(jìn)隊列，　　//遍歷完所有的鄰接頂點(diǎn)，出隊列　　}　　v

26、oid BFStraversal(Graph *G,char c)//顯示圖的遍歷結(jié)果　　void main()　　{　　Graph * G=new Graph;　　CreatAdjList(G);<p&

27、gt;　　char ch;　　cout<<"請輸入開始遍歷的頂點(diǎn):";　　cin>>ch;　　BFStraversal(G,ch);

28、　}//執(zhí)行主函數(shù)　　調(diào)試過程　　1．在求圖的第u個頂點(diǎn)，與其相鄰的一系列頂點(diǎn)中，第w個頂點(diǎn)的下一個頂點(diǎn)時，若是求最后一個頂點(diǎn)的下一個頂點(diǎn)時，函數(shù)進(jìn)入了死循環(huán)。原因是判斷條件沒有寫好，造成了判斷值恒為真，因此進(jìn)入了死循環(huán)。修改后，函數(shù)正常運(yùn)行。　　2．廣度

29、優(yōu)先遍歷圖的時候，是從指定的任一頂點(diǎn)開始遍歷，當(dāng)遇到該圖為無向非連通圖，并不能把該圖遍歷。　　原因是沒有寫出一個循環(huán)體，去嘗試遍歷其他沒有被遍歷的頂點(diǎn)。加上這樣一個循環(huán)體后，便可以遍歷任意一種圖了，并且還可以在此基礎(chǔ)上算出圖的兩通分量。　　3．在輸入圖信息的時候，若輸入非法字符，程序會異常終止。例如程序要求輸入一個整型，用戶卻輸入了一個字母，這時候會出現(xiàn)

30、異常。只是程序是否健壯性的一個體現(xiàn)。采用輸入流的一些函數(shù)，便可以解決這一問題。還有其他一些類似的輸入異常，都是采用類似的處理方法。　　4．作為一個完整的程序，友好的界面是必須的。因次程序中適當(dāng)?shù)夭捎孟到y(tǒng)中的清屏命令，使得界面更加簡潔，明了。　　5.判斷隊列的空或者滿的時候注意，對頭指針和隊尾指針為多少。<b

31、>　　經(jīng)驗與體會　　本次試驗采用的是用鄰接表的方式對無向圖進(jìn)行廣度優(yōu)先遍歷，通過本次課程設(shè)計，學(xué)會了應(yīng)用書本上的知識來進(jìn)行實(shí)踐活動，同時也發(fā)現(xiàn)了自己的理論知識并不健全，并且也無法靈活應(yīng)用，這些教育著我們以后得花更多的時間和精力去學(xué)習(xí)書本上的理論知識，并及時學(xué)會靈活應(yīng)用。　　在寫程序之前應(yīng)該好好理解關(guān)于圖的鄰接表存儲結(jié)構(gòu)的特點(diǎn)和廣

32、度優(yōu)先遍歷的原理。　　附源程序清單和運(yùn)行結(jié)果　　#include<iostream.h>　　#define MaxVerNum 50 　　struct edgenode　　{<

33、;/p>　　int endver;　　int inform;　　edgenode* edgenext; 　　};　　struct vexnode

34、;　　{　　char vertex;　　edgenode* edgelink;　　};　　struct Graph 　　{<

35、/p>　　vexnode adjlists[MaxVerNum];　　int vexnum;　　int arcnum;　　};　　//隊列的定義及相關(guān)函數(shù)的實(shí)現(xiàn)

36、struct QueueNode　　{　　int nData;　　QueueNode* next;　　};　　struct QueueList </

37、p>　　{　　QueueNode* front;　　QueueNode* rear;　　};　　void EnQueue(QueueList* Q,int e)<

38、/p>　　{　　QueueNode *q=new QueueNode;　　q->nData=e;　　q->next=NULL;　　if(Q==NULL)

39、　　return;　　if(Q->rear==NULL)　　Q->front=Q->rear=q;　　else　　{

40、　　Q->rear->next=q;　　Q->rear=Q->rear->next;　　}　　}　　void DeQueue(QueueList*

41、Q,int* e)　　{　　if (Q==NULL)　　return;　　if (Q->front==Q->rear)　　{

42、　　*e=Q->front->nData;　　Q->front=Q->rear=NULL;　　}　　else&

43、lt;b>　　{　　*e=Q->front->nData;　　Q->front=Q->front->next;　　}　　}

44、;　　//創(chuàng)建圖　　void CreatAdjList(Graph* G)　　{　　int i,j,k;　　edgenode* p1;

45、;　　edgenode* p2;　　cout<<"請輸入頂點(diǎn)數(shù)和邊數(shù):"<<endl;　　cin>>G->vexnum>>G->arcnum;　　cout<<"開始輸入頂點(diǎn)表:"<<endl

46、;　　for (i=0;i<G->vexnum;i++)　　{　　cin>>G->adjlists[i].vertex;　　G->adjlists[i].edgelink=NULL;</p&g

47、t;　　}　　cout<<"開始輸入邊表信息:"<<endl;　　for (k=0;k<G->arcnum;k++)　　{<p&g

48、t;　　cout<<"請輸入邊<Vi,Vj>對應(yīng)的頂點(diǎn):";　　cin>>i>>j;　　p1=new edgenode;　　p1->endver=j;　　p1->edgenext=G->

49、adjlists[i].edgelink;　　G->adjlists[i].edgelink=p1;　　p2=new edgenode;　　p2->endver=i;　　p2->edgenext=G->adjlists[j].edgelink;&l

50、t;/p>　　G->adjlists[j].edgelink=p2;　　//因為是無向圖，所以有兩次建立邊表的過程　　}　　}　　//--------------

51、-----------------------------------------------深度優(yōu)先遍歷　　void DFS(Graph *G,int i,int visit[])　　{　　cout<<G->adjlists[i].vertex<&l

52、t;" ";　　visit[i]=1;　　edgenode *p=new edgenode;　　p=G->adjlists[i].edgelink;　　if(G->adjlists[i].edgelink&&!visit[p

53、->endver])　　{　　DFS(G,p->endver,visit);　　}　　}　　void

54、DFStraversal(Graph *G,char c)//深度優(yōu)先遍歷　　{　　cout<<"該圖的深度優(yōu)先遍歷結(jié)果為:"<<endl;　　int visit[MaxVerNum];

55、for(int i=0;i<G->vexnum;i++)　　{　　visit[i]=0;//全部初始化為0，即未訪問狀態(tài)　　}　　int m;&l

56、t;/p>　　for (i=0;i<G->vexnum;i++)　　{　　if (G->adjlists[i].vertex==c)//根據(jù)字符查找序號　　{<p

57、>　　m=i;　　DFS(G,i,visit);　　break;　　}　　}<p&g

58、t;　　//繼續(xù)訪問未被訪問的結(jié)點(diǎn)　　for(i=0;i<G->vexnum;i++)　　{　　if(visit[i]==0)　　DFS(G,i,visit);

59、　}　　cout<<endl;　　}　　//-------------------------------------------------------------廣度優(yōu)先遍歷　　void BFS(

60、Graph* G,int v,int visit[])　　{　　QueueList *Q=new QueueList;　　Q->front=Q->rear=NULL;　　EnQueue(Q,v);&

61、lt;p>　　while(Q->rear!=NULL)　　{　　int e=0;　　DeQueue(Q,&e);　　cout<<G->adjlists[e].

62、vertex<<" ";　　visit[e]=1;　　edgenode* p=new edgenode;　　p=G->adjlists[e].edgelink;　　if(p)

63、　　{　　int m=p->endver;　　if(m==0)　　{　　EnQueue(Q,m);<p

64、>　　while(visit[m]==0)　　{　　p=p->edgenext;　　if(p==NULL)　　break;　　m=p->

65、endver;　　EnQueue(Q,m);　　}　　}　　}　　}</

66、p>　　}　　void BFStraversal(Graph *G,char c)　　{　　cout<<"該圖的廣度優(yōu)先遍歷結(jié)果為:"<<endl;

67、;　　int visited[MaxVerNum];　　for (int i=0;i<G->vexnum;i++)　　{　　visited[i]=0;　　}<

68、;/p>　　int m;　　for (i=0;i<G->vexnum;i++)　　{　　if (G->adjlists[i].vertex==c)&l

69、t;b>　　{　　m=i;　　BFS(G,i,visited);　　break;　　}&l

70、t;b>　　}　　//繼續(xù)訪問未被訪問的結(jié)點(diǎn)　　for(i=0;i<G->vexnum;i++)　　{　　if(visited[i]==0)　　BFS(G

71、,i,visited);　　}　　cout<<endl;　　}　　void main()　　{</

72、p>　　Graph * G=new Graph;　　CreatAdjList(G);　　char ch;　　cout<<"請輸入開始遍歷的頂點(diǎn):";　　ci

眾賞文庫> 全部分類> 畢業(yè)設(shè)計

溫馨提示

1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
3. 本站RAR壓縮包中若帶圖紙，網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽，若沒有圖紙預(yù)覽就沒有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 眾賞文庫僅提供信息存儲空間，僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理，對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對任何下載內(nèi)容負(fù)責(zé)。
6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容，請與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

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

文檔簡介

溫馨提示

最新文檔

評論

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

文檔簡介

溫馨提示

最新文檔

評論

免費(fèi)下載