采用鄰接表存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)圖的廣度優(yōu)先遍歷

1、課程設(shè)計(jì)題目九：圖的廣度優(yōu)先遍歷基本要求：采用鄰接表存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)圖的廣度優(yōu)先遍歷。（2）對(duì)任意給定的圖（頂點(diǎn)數(shù)和邊數(shù)自定），建立它的鄰接表并輸出；（3）實(shí)現(xiàn)圖的廣度優(yōu)先遍歷*/#include<iostream.h>#include<stdio.h>#include<malloc.h>#define MAX_NUM 20int visitedMAX_NUM=0;typedef int VertexType;typedef enum DG=1,UDGGraphKind;typedef struct ArcNodeint adjvex;int weight;st

2、ruct ArcNode *nextarc;ArcNode *info;ArcNode;typedef struct VNodeVertexType data;ArcNode *firstarc;VNode,AdjListMAX_NUM;typedef structAdjList vertices;int vexnum,arcnum;GraphKind kind;ALGraph;void PRIN(ALGraph &G);void Creat_adjgraph(ALGraph &G);void bfs(ALGraph &G,int v);void Creat_adjgr

3、aphDG(ALGraph &G);void Creat_adjgraphUDG(ALGraph &G);void Creat_adjgraph(ALGraph &G);void Creat_adjgraphDG(ALGraph &G)int i,s,d;ArcNode *p=NULL,*q=NULL;G.kind=DG;printf("請(qǐng)輸入頂點(diǎn)數(shù)和邊數(shù)：");scanf("%d %d",&G.vexnum,&G.arcnum);for(i=0;i<G.vexnum;+i)printf("

4、第%d個(gè)頂點(diǎn)信息：",i+1);scanf("%d",&G.verticesi.data);G.verticesi.firstarc=NULL;for(i=0;i<G.arcnum;+i)printf("第%d條邊的起始頂點(diǎn)編號(hào)和終止頂點(diǎn)編號(hào)：",i+1);scanf("%d %d",&s,&d);while(s<1|s>G.vexnum|d<1|d>G.vexnum)printf("編號(hào)超出范圍，重新輸入");scanf("%d%d&quo

5、t;,&s,&d);s-;d-;p=new(ArcNode);p->adjvex=d;p->nextarc=G.verticess.firstarc;G.verticess.firstarc=p;void Creat_adjgraphUDG(ALGraph &G)int i,s,d;ArcNode *p,*q;G.kind=UDG;printf("請(qǐng)輸入頂點(diǎn)數(shù)和邊數(shù)：");scanf("%d %d",&G.vexnum,&G.arcnum);for(i=0;i<G.vexnum;+i)printf

6、("第%d個(gè)頂點(diǎn)信息：",i+1);scanf("%d",&G.verticesi.data);G.verticesi.firstarc=NULL;for(i=0;i<G.arcnum;+i)printf("第%d條邊的起始頂點(diǎn)編號(hào)和終止頂點(diǎn)編號(hào)：",i+1);scanf("%d %d",&s,&d);while(s<1|s>G.vexnum|d<1|d>G.vexnum)printf("編號(hào)超出范圍，重新輸入");scanf("%

7、d %d",&s,&d);s-;d-;p=new(ArcNode);p->adjvex=d;p->nextarc=G.verticess.firstarc;G.verticess.firstarc=p;q=new(ArcNode);q->adjvex=s;q->nextarc=G.verticesd.firstarc;G.verticesd.firstarc=q;void PRIN(ALGraph &G)int i;ArcNode *p;if(G.kind=DG|G.kind=UDG)for(i=0;i<G.vexnum;+i)p

8、rintf("V%d:",G.verticesi.data);p=G.verticesi.firstarc;while(p!=NULL)printf("%dt",p->adjvex+1);p=p->nextarc;printf("n");void bfs(ALGraph &G,int v)v-;ArcNode *p;int queueMAX_NUM,front=0,rear=0;int w,i;for(i=0;i<G.vexnum;i+)visitedi=0;printf("%4d",v+

9、1);visitedv=1;rear=(rear+1)%MAX_NUM;queuerear=v;while(front!=rear)front=(front+1)%MAX_NUM;w=queuefront;p=G.verticesw.firstarc;while(p!=NULL)if(visitedp->adjvex=0)printf("%3d",p->adjvex+1);visitedp->adjvex=1;rear=(rear+1)%MAX_NUM;queuerear=p->adjvex;p=p->nextarc;printf("n");void Creat_adjgraph(ALGraph &G)printf("1：有向圖 2：無向圖n");printf("請(qǐng)根據(jù)上述提示輸入圖的類型：");scanf("%d",&G.kind);switch (G.kind)case DG:Creat_adjgraphDG(G);PRIN(G);break;case UDG:Creat_adjgraphUDG(G);PRIN(G);break;default:pri