圖的廣度遍歷課程設(shè)計(jì)報(bào)告-展示頁(yè)
2025-04-01 06:21本頁(yè)面
【正文】 G,u)。//v入隊(duì)列 while(!()) { int u = ()。 Visit(v)。vn。 while(!()) ()。void print(int v)//輸出頂點(diǎn)信息int FirstAdjVex(ALGraph G,int u)//在鄰接表G中取第u個(gè)頭結(jié)點(diǎn)void NextAdjVex(ALGraph G,int u,int w)// 在鄰接表G中取第u個(gè)頭結(jié)點(diǎn)之后的結(jié)點(diǎn)w的下一結(jié)點(diǎn)void BFSTraverse(ALGraph G,queueint Q,bool visited[],int m,int n,void (*Visit)(int))//使用輔助隊(duì)列Q從鄰接表結(jié)點(diǎn)m開始n結(jié)束廣度遍歷鄰接表圖G void BFSTraverse(ALGraph G,queueint Q,bool visited[],int m,int n,void (*Visit)(int))//使用輔助隊(duì)列Q從鄰接表結(jié)點(diǎn)m開始n結(jié)束廣度遍歷鄰接表圖G{ //按廣度優(yōu)先非遞歸遍歷圖G。//圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù) int kind。typedef struct//圖{ AdjList Vertices。//結(jié)點(diǎn)信息 ArcNode *firstarc。//該弧相關(guān)信息指針}ArcNode。//該弧所指向的頂點(diǎn)位置 struct ArcNode *nextarc。之后決定是否繼續(xù)遍歷該圖或輸入另一個(gè)需要遍歷的圖亦或是結(jié)束程序。然后輸入圖的頂點(diǎn)數(shù)、邊數(shù)和各條邊，之后生成該圖的鄰接表并輸出。 （3）畫出搜索順序示意圖。目 錄 1 1 1 2 流程圖 2 、函數(shù)及說明 3 4 4 4 5 6 7 16 16 16 、結(jié)果截圖： 17 ： 17 （案例一）測(cè)試： 20 （案例二）測(cè)試： 22 24參考文獻(xiàn) 25 25 （1）對(duì)任意給定的圖（頂點(diǎn)數(shù)和邊數(shù)自定），建立它的鄰接表并輸出。（2）然后利用隊(duì)列的五種基本運(yùn)算（置空隊(duì)列、進(jìn)隊(duì)、出隊(duì)、取隊(duì)頭元素、判隊(duì)空）實(shí)現(xiàn)圖的廣度優(yōu)先搜索遍歷。 （1）首先輸入圖的類型，有向或無向圖（因?yàn)楸闅v與權(quán)值無關(guān)，所以沒有涉及帶權(quán)圖）。（2）再輸入要遍歷該圖的起點(diǎn)，然后從所輸入的點(diǎn)廣度搜索該圖的鄰接表，并按遍歷順序輸出頂點(diǎn)內(nèi)容。 開始輸入圖的類型確定圖的類型輸入無向圖輸入有向圖輸入從哪個(gè)頂點(diǎn)開始遍歷該圖廣度優(yōu)先遍歷該圖是否從其他頂點(diǎn)開始重新遍歷該圖 是 否是否結(jié)束 否 是結(jié)束 圖 21 流程圖 、函數(shù)及說明typedef struct ArcNode//鄰接表表結(jié)點(diǎn){ int adjvex。//指向下一條弧的指針 //InfoType *info。typedef struct VNode//鄰接表頭結(jié)點(diǎn){ VertexType data。//指向第一條依附該結(jié)點(diǎn)的弧的指針}VNode,AdjList[MAX_VERTEX_NUM]。//鄰接表頭結(jié)點(diǎn)數(shù)組 int vexnum,arum。//圖的種類標(biāo)志(有向圖:0,無向圖:1)}ALGraph。使用輔助隊(duì)列Q和訪問標(biāo)志數(shù)組visited。//置空的輔助隊(duì)列Q for(int v=m。++v) if(!visited[v])//如果v尚未訪問 { visited[v]=true。//訪問v (v)。 ()。 w = 0。 Visit(w)。//w入隊(duì)列 }//if }//while }//if}//BFSTraverse*/ cout\n請(qǐng)輸入圖的弧數(shù):。) { gets_s(s)。//取出字符串中的整型 n=*()/2。//修正整型合理范圍 if(tn||t1)//如果整型不在合理范圍內(nèi) cout錯(cuò)誤!請(qǐng)輸入一個(gè)大于0小于n+1的數(shù):。//跳出循環(huán)繼續(xù) } =t。 for(int i=0。i++) { int n1,n2。) { cout弧i+1:\t。//以字符串形式接受所輸入的數(shù)據(jù) t=atoi(s)。//去掉字符串中的前兩個(gè)字符 n=atoi(c)
電大資料相關(guān)推薦
鄂ICP備17016276號(hào)-1