為圖建立鄰接表,深度與廣度遍歷

《為圖建立鄰接表,深度與廣度遍歷》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、為一個(gè)圖建立一個(gè)鄰接表、編寫深度遍歷和廣度遍歷算法#include#include#defineMaxNode40#defineM20typedefstructArcNode{intadjvex;structArcNode*nextarc;}ArcNode;typedefstruct{intvertex;structArcNode*firstarc;}vernode;typedefvernodeadjlist[MaxNode];intqueue[MaxNode];//在遍歷過程中是從右邊開始voiddfs

2、(adjlistg,intk,intvisited[])//從頂點(diǎn)k出發(fā)，深度優(yōu)先搜索{ArcNode*p;intw;visited[k]=1;printf("%d->",g[k].vertex);p=g[k].firstarc;while(p!=NULL){w=p->adjvex;if(visited[w]==0)dfs(g,w,visited);p=p->nextarc;}}voidbfs(adjlistg,intk,intvisited[])//從頂點(diǎn)k出發(fā)，廣度優(yōu)先搜索{intfront=0,rear=1,w;ArcNode*p;vi

3、sited[k]=1;//訪問初始頂點(diǎn)printf("%d->",k);queue[rear]=k;//初始頂點(diǎn)入隊(duì)列while(front!=rear)//隊(duì)列不為空{(diào)front=(front+1)%M;w=queue[front];//按訪問次序依次出隊(duì)列p=g[w].firstarc;while(p!=NULL){if(visited[p->adjvex]==0){visited[p->adjvex]=1;printf("%d->",p->adjvex);rear=(rear+1)%M;queue[rear]=p->adjvex;;}p

4、=p->nextarc;}}}voidtrave_bfs(adjlistg,intn){inti,visited[MaxNode];//數(shù)組visited標(biāo)志圖中的頂點(diǎn)是否已被訪問for(i=1;i<=n;i++)visited[i]=0;for(i=1;i<=n;i++)if(visited[i]==0)bfs(g,i,visited);printf("bb");}voidtrave_dfs(adjlistg,intn){inti,visited[MaxNode];//數(shù)組visited標(biāo)志圖中的頂點(diǎn)是否已被訪問for(i=1;i<

5、=n;i++)visited[i]=0;for(i=1;i<=n;i++)if(visited[i]==0)dfs(g,i,visited);printf("bb");}voidprint(adjlistg,intn){ArcNode*q;inti;printf("輸出無向圖的鄰接鏈表示：");for(i=1;i<=n;i++){printf("t%dt",i);printf("%d->",g[i].vertex);q=g[i].firstarc;while(q!=NULL){printf("%d->",q->adjvex);

6、q=q->nextarc;}printf("bb");}}voidmain(){ArcNode*p,*q;adjlistg;inti,j,n,k,e;printf("輸入圖中頂點(diǎn)的個(gè)數(shù),邊數(shù):");scanf("%d%d",&n,&e);for(k=1;k<=n;k++){getchar();printf("t第%d個(gè)頂點(diǎn)信息:",k);scanf("%d",&g[k].vertex);g[k].firstarc=NULL;//對順序存儲部分初始化}for(k=1;k<=e;k++){printf("第%d條邊的起點(diǎn),終點(diǎn):",k)

7、;scanf("%d%d",&i,&j);q=(ArcNode*)malloc(sizeof(ArcNode));q->adjvex=j;q->nextarc=g[i].firstarc;g[i].firstarc=q;p=(ArcNode*)malloc(sizeof(ArcNode));p->adjvex=i;p->nextarc=g[j].firstarc;g[j].firstarc=p;}print(g,n);printf("");printf("圖的深度優(yōu)先搜索:");trave_dfs(g,n);printf("");pr

8、intf("圖的廣度優(yōu)先搜索:");trave_bfs(g,n);printf("");