【正文】 目 錄 1 1 1 2 流程圖 2 、函數及說明 3 4 4 4 5 6 7 16 16 16 、結果截圖： 17 ： 17 （案例一）測試： 20 （案例二）測試： 22 24參考文獻 25 25 （1）對任意給定的圖（頂點數和邊數自定），建立它的鄰接表并輸出。（2）然后利用隊列的五種基本運算（置空隊列、進隊、出隊、取隊頭元素、判隊空）實現圖的廣度優(yōu)先搜索遍歷。 （3）畫出搜索順序示意圖。 （1）首先輸入圖的類型，有向或無向圖（因為遍歷與權值無關，所以沒有涉及帶權圖）。然后輸入圖的頂點數、邊數和各條邊，之后生成該圖的鄰接表并輸出。（2）再輸入要遍歷該圖的起點，然后從所輸入的點廣度搜索該圖的鄰接表，并按遍歷順序輸出頂點內容。之后決定是否繼續(xù)遍歷該圖或輸入另一個需要遍歷的圖亦或是結束程序。 開始輸入圖的類型確定圖的類型輸入無向圖輸入有向圖輸入從哪個頂點開始遍歷該圖廣度優(yōu)先遍歷該圖是否從其他頂點開始重新遍歷該圖 是 否是否結束 否 是結束 圖 21 流程圖 、函數及說明typedef struct ArcNode//鄰接表表結點{ int adjvex。//該弧所指向的頂點位置 struct ArcNode *nextarc。//指向下一條弧的指針 //InfoType *info。//該弧相關信息指針}ArcNode。typedef struct VNode//鄰接表頭結點{ VertexType data。//結點信息 ArcNode *firstarc。//指向第一條依附該結點的弧的指針}VNode,AdjList[MAX_VERTEX_NUM]。typedef struct//圖{ AdjList Vertices。//鄰接表頭結點數組 int vexnum,arum。//圖的當前頂點數和弧數 int kind。//圖的種類標志(有向圖:0,無向圖:1)}ALGraph。void print(int v)//輸出頂點信息int FirstAdjVex(ALGraph G,int u)//在鄰接表G中取第u個頭結點void NextAdjVex(ALGraph G,int u,int w)// 在鄰接表G中取第u個頭結點之后的結點w的下一結點void BFSTraverse(ALGraph G,queueint Q,bool visited[],int m,int n,void (*Visit)(int))//使用輔助隊列Q從鄰接表結點m開始n結束廣度遍歷鄰接表圖G void BFSTraverse(ALGraph G,queueint Q,bool visited[],int m,int n,void (*Visit)(int))//使用輔助隊列Q從鄰接表結點m開始n結束廣度遍歷鄰接表圖G{ //按廣度優(yōu)先非遞歸遍歷圖G。使用輔助隊列Q和訪問標志數組visited。 while(!()) ()。//置空的輔助隊列Q for(int v=m。vn。++v) if(!visited[v])//如果v尚未訪問 { visited[v]=true。 Visit(v)。//訪問v (v)。//v入隊列 while(!()) { int u = ()。 ()。//對頭元素出隊并置為u for( int w = FirstAdjVex(G,u)。 w = 0。 w = NextAdjVex(G,u,w))//從以u為頭結點的鄰接表開始遍歷到鏈表中的最后一個結點 if(!visited[w])//w為u的尚未訪問的鄰接結點 { visited[w]=true。 Visit(w)。//訪問w (w)。//w入隊列 }//if }//while }//if}//BFSTraverse*/ cout\n請輸入圖的弧數:。 for(。) { gets_s(s)。//以字符串形式接受所輸入的數據 t=atoi(s)。//取出字符串中的整型 n=*()/2。//計算整型合理范圍