采用邻接表存储结构实现图的广度优先遍历

采用邻接表存储结构实现图的广度优先遍历。采用邻接表存储结构实现图的广度优先遍历。采用邻接表存储结构实现图的广度优先遍历。V:1.0精细整理，仅供参考采用邻接表存储结构实现图的广度优先遍历。日期：20xx年X月课程设计题目九：图的广度优先遍历基本要求：采用邻接表存储结构实现图的广度优先遍历。（2）对任意给定的图（顶点数和边数自定），建立它的邻接表并输出；（3）实现图的广度优先遍历*/#include<>#include<>#include<>#defineMAX_NUM20intvisited[MAX_NUM]={0};typedefintVertexType;typedefenum{DG=1,UDG}GraphKind;typedefstructArcNode{ intadjvex; intweight; structArcNode*nextarc; ArcNode*info;}ArcNode;typedefstructVNode{ VertexTypedata; ArcNode*firstarc;}VNode,AdjList[MAX_NUM];typedefstruct{ AdjListvertices; intvexnum,arcnum; GraphKindkind;}ALGraph;voidPRIN(ALGraph&G);voidCreat_adjgraph(ALGraph&G);voidbfs(ALGraph&G,intv);voidCreat_adjgraphDG(ALGraph&G);voidCreat_adjgraphUDG(ALGraph&G);voidCreat_adjgraph(ALGraph&G);voidCreat_adjgraphDG(ALGraph&G){ inti,s,d; ArcNode*p=NULL,*q=NULL;=DG; printf("请输入顶点数和边数："); scanf("%d%d",&,&; for(i=0;i<;++i) { printf("第%d个顶点信息：",i+1); scanf("%d",&[i].data); [i].firstarc=NULL;} for(i=0;i<;++i) { printf("第%d条边的起始顶点编号和终止顶点编号：",i+1); scanf("%d%d",&s,&d); while(s<1||s>||d<1||d> { printf("编号超出范围，重新输入"); scanf("%d%d",&s,&d);} s--; d--; p=new(ArcNode); p->adjvex=d; p->nextarc=[s].firstarc; [s].firstarc=p; }}voidCreat_adjgraphUDG(ALGraph&G){ inti,s,d; ArcNode*p,*q; =UDG; printf("请输入顶点数和边数："); scanf("%d%d",&,&; for(i=0;i<;++i) { printf("第%d个顶点信息：",i+1); scanf("%d",&[i].data); [i].firstarc=NULL;} for(i=0;i<;++i) { printf("第%d条边的起始顶点编号和终止顶点编号：",i+1); scanf("%d%d",&s,&d); while(s<1||s>||d<1||d> { printf("编号超出范围，重新输入"); scanf("%d%d",&s,&d);} s--; d--; p=new(ArcNode); p->adjvex=d; p->nextarc=[s].firstarc; [s].firstarc=p; q=new(ArcNode); q->adjvex=s; q->nextarc=[d].firstarc; [d].firstarc=q; }}voidPRIN(ALGraph&G){ inti; ArcNode*p; if==DG||==UDG) { for(i=0;i<;++i) { printf("V%d:",[i].data); p=[i].firstarc; while(p!=NULL) { printf("%d\t",p->adjvex+1); p=p->nextarc;} printf("\n");} }}voidbfs(ALGraph&G,intv){ v--; ArcNode*p; intqueue[MAX_NUM],front=0,rear=0; intw,i; for(i=0;i<;i++)visited[i]=0; printf("%4d",v+1); visited[v]=1; rear=(rear+1)%MAX_NUM; queue[rear]=v; while(front!=rear) { front=(front+1)%MAX_NUM; w=queue[front]; p=[w].firstarc; while(p!=NULL) { if(visited[p->adjvex]==0) { printf("%3d",p->adjvex+1); visited[p->adjvex]=1; rear=(rear+1)%MAX_NUM; queue[rear]=p->adjvex;} p=p->nextarc;} } printf("\n");}voidCreat_adjgraph(ALGraph&G){ printf("1：有向图2：无向图\n"); printf("请根据上述提示输入图的类型：" ); scanf("%d",&; switch { caseDG:Creat_adjgraphDG(G);PRIN(G);break; caseUDG:Creat_adjgraphUDG(G);PRIN(G);break;