圖的廣度遍歷課程設(shè)計報告(編輯修改稿)
2025-04-19 06:21 本頁面
【文章內(nèi)容簡介】 int kind。//圖的種類標(biāo)志(有向圖:0,無向圖:1)}ALGraph。void print(int v)//輸出頂點信息{ coutv+1 。}int FirstAdjVex(ALGraph G,int u)//在鄰接表G中取第u個頭頂點{ if([u].firstarc==NULL) return 1。 return [u].firstarcadjvex。}int NextAdjVex(ALGraph G,int u,int w)// 在鄰接表G中取第u個頭頂點之后的頂點w的下一頂點{ ArcNode *p = [u].firstarc。 while(w != padjvex) p = pnextarc。 if(pnextarc==NULL)return 1。 return pnextarcadjvex。}void BFSTraverse(ALGraph G,queueint Q,bool visited[],int m,int n,void (*Visit)(int))//使用輔助隊列Q從鄰接表頂點m開始n結(jié)束廣度遍歷鄰接表圖G{ //按廣度優(yōu)先非遞歸遍歷圖G。使用輔助隊列Q和訪問標(biāo)志數(shù)組visited。 while(!()) ()。//置空的輔助隊列Q for(int v=m。vn。++v) if(!visited[v])//v尚未訪問 { visited[v]=true。 Visit(v)。 (v)。//v入隊列 while(!()) { int u = ()。 ()。//對頭元素出隊并置為u for( int w = FirstAdjVex(G,u)。 w = 0。 w = NextAdjVex(G,u,w)) if(!visited[w])//w為u的尚未訪問的鄰接頂點 { visited[w]=true。 Visit(w)。 (w)。 }//if }//while }//if}//BFSTraverse*/int main(){ int t,n。 char s[10],c[10]。 ALGraph G。 do { system(cls)。 cout請輸入圖的類型(有向圖輸1,無向圖輸2):。 for(。) { gets_s(s)。 t=atoi(s)。 if(t!=1amp。amp。t!=2) cout錯誤!請輸入半角數(shù)字\1\或\2\:。 else break。 } =t。 cout\n請輸入圖的頂點數(shù):。 for(。) { gets_s(s)。 t=atoi(s)。 if(t99||t1) cout錯誤!請輸入一個大于0小于100的數(shù):。 else break。 } =t。 bool visited[MAX_VERTEX_NUM]。 for(int i=0。i。i++) { visited[i]=false。 [i].firstarc=NULL。 } if(==1) { cout\n請輸入圖的弧數(shù):。 for(。) { gets_s(s)。 t=atoi(s)。 n=*()/2。 if(==1) n+=n。 if(tn||t1) cout錯誤!請輸入一個大于0小于n+1的數(shù):。 else break。 } =t。 cout\n請分別輸入圖的條弧(弧尾，弧頭):endl。 for(int i=0。i。i++) { int n1,n2。 for(。) { cout弧i+1:\t。 gets_s(s)。 strcpy_s(c,s)。 t=atoi(c)。 strcpy_s(c,s+2)。 n=atoi(c)。 if(t||t1||n||n1||t==n) cout錯誤!請分別輸入兩個大于0小于+1的數(shù):\n\n。 else break。 } n1=t1。n2=n1。 if(!visited[n1]) { visited[n1]=true。 [n1].firstarc = new ArcNode。 [n1].firstarcadj
電大資料相關(guān)推薦
鄂ICP備17016276號-1