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

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

2023年全國(guó)碩士研究生考試考研英語(yǔ)一試題真題（含答案詳解+作文范文）_第1頁(yè)

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

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

文檔簡(jiǎn)介

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

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

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

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

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

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

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

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

9、t;　　畫(huà)出下圖所示的無(wú)向圖的鄰接表，使得其中每個(gè)無(wú)項(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)序列和邊的序列。　　2.2問(wèn)題分析和任務(wù)定義　　圖的鄰接表表示：在第i行的單鏈表中，各結(jié)點(diǎn)（稱(chēng)作邊結(jié)點(diǎn)）分別存放與同一

10、個(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ā)訪問(wèn)圖中所有頂點(diǎn)，且使得每一頂點(diǎn)僅被訪問(wèn)一次，這個(gè)過(guò)程稱(chēng)為圖的遍歷。圖的遍歷是從圖中某個(gè)頂點(diǎn)出發(fā)，沿著某條搜索路徑對(duì)圖中其余每個(gè)頂點(diǎn)進(jìn)行訪問(wèn), 并且使圖中的每個(gè)頂點(diǎn)僅被訪問(wèn)一次的過(guò)程。

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

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

13、1，Vi2…，Vit的鄰接點(diǎn)中未經(jīng)訪問(wèn)過(guò)的頂點(diǎn)，依此類(lèi)推，直到圖中所有頂點(diǎn)均被訪問(wèn)為止。　　4.2.2具體過(guò)程：　　從廣度優(yōu)先搜索遍歷方法可知，先被訪問(wèn)的頂點(diǎn)的鄰接點(diǎn)也被訪問(wèn)，即假設(shè)頂點(diǎn)V在W之前被訪問(wèn)，那么頂點(diǎn)V的所有未經(jīng)訪問(wèn)的鄰接點(diǎn)也在頂點(diǎn)W的所有未經(jīng)訪問(wèn)的鄰接點(diǎn)之前被訪問(wèn)。這樣可以在廣度優(yōu)先遍歷的算法中設(shè)置一個(gè)隊(duì)列結(jié)構(gòu)，用以保存已訪問(wèn)過(guò)的頂點(diǎn)的序號(hào)

14、，訪問(wèn)該頂點(diǎn)的所有未經(jīng)訪問(wèn)的頂點(diǎn)。　　廣度優(yōu)先搜索是一種分層的搜索過(guò)程，每向前走一步可能訪問(wèn)一批頂點(diǎn)，不像深度優(yōu)先搜索那樣會(huì)出現(xiàn)回退的現(xiàn)象。因此它不是個(gè)遞歸的過(guò)程。為了實(shí)現(xiàn)逐層訪問(wèn)，算法中使用了一個(gè)隊(duì)列以記憶正在訪問(wèn)的這一層和上一層的頂點(diǎn)，以便于向下一層訪問(wèn)。為了避免重復(fù)訪問(wèn)，需要一個(gè)輔助函數(shù)visitvex[]給被訪問(wèn)過(guò)的頂點(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)體　　//隊(duì)列的定義及

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

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

19、;p>　　else　　{//將尾指針的連接到q上，在使尾指針指向向一個(gè)節(jié)點(diǎn)}　　}　　void DeQueue(QueueList* Q,int* e)//實(shí)現(xiàn)隊(duì)列的進(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++)　　{　　請(qǐng)輸入邊<Vi,Vj>對(duì)應(yīng)的頂點(diǎn)　　//因?yàn)槭菬o(wú)向圖，所以有兩次建立邊表的過(guò)程　　}

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

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

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

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

28、　}//執(zhí)行主函數(shù)　　調(diào)試過(guò)程　　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)。原因是判斷條件沒(méi)有寫(xiě)好，造成了判斷值恒為真，因此進(jìn)入了死循環(huán)。修改后，函數(shù)正常運(yùn)行。　　2．廣度

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

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

31、>　　經(jīng)驗(yàn)與體會(huì)　　本次試驗(yàn)采用的是用鄰接表的方式對(duì)無(wú)向圖進(jìn)行廣度優(yōu)先遍歷，通過(guò)本次課程設(shè)計(jì)，學(xué)會(huì)了應(yīng)用書(shū)本上的知識(shí)來(lái)進(jìn)行實(shí)踐活動(dòng)，同時(shí)也發(fā)現(xiàn)了自己的理論知識(shí)并不健全，并且也無(wú)法靈活應(yīng)用，這些教育著我們以后得花更多的時(shí)間和精力去學(xué)習(xí)書(shū)本上的理論知識(shí)，并及時(shí)學(xué)會(huì)靈活應(yīng)用。　　在寫(xiě)程序之前應(yīng)該好好理解關(guān)于圖的鄰接表存儲(chǔ)結(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;　　};　　//隊(duì)列的定義及相關(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<<"請(qǐng)輸入頂點(diǎn)數(shù)和邊數(shù):"<<endl;　　cin>>G->vexnum>>G->arcnum;　　cout<<"開(kāi)始輸入頂點(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<<"開(kāi)始輸入邊表信息:"<<endl;　　for (k=0;k<G->arcnum;k++)　　{<p&g

48、t;　　cout<<"請(qǐng)輸入邊<Vi,Vj>對(duì)應(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;　　//因?yàn)槭菬o(wú)向圖，所以有兩次建立邊表的過(guò)程　　}　　}　　//--------------

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，即未訪問(wèn)狀態(tài)　　}　　int m;&l

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

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

58、t;　　//繼續(xù)訪問(wèn)未被訪問(wèn)的結(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ù)訪問(wèn)未被訪問(wèn)的結(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<<"請(qǐng)輸入開(kāi)始遍歷的頂點(diǎn):";　　ci

眾賞文庫(kù)> 全部分類(lèi)> 畢業(yè)設(shè)計(jì)

溫馨提示

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

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

文檔簡(jiǎn)介

溫馨提示

最新文檔

評(píng)論

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

文檔簡(jiǎn)介

溫馨提示

最新文檔

評(píng)論

免費(fèi)下載