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

课程设计题目九：图的广度优先遍历基本要求：采用邻接表存储结构实现图的广度优先遍历。（2）对任意给定的图（顶点数和边数自定），建立它的邻接表并输出；（3）实现图的广度优先遍历*/#includeiostream.h#includestdio.h#includemalloc.h#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;G.kind=DG;printf(请输入顶点数和边数：);scanf(%d%d,&G.vexnum,&G.arcnum);for(i=0;iG.vexnum;++i){printf(第%d个顶点信息：,i+1);scanf(%d,&G.vertices[i].data);G.vertices[i].firstarc=NULL;}for(i=0;iG.arcnum;++i){printf(第%d条边的起始顶点编号和终止顶点编号：,i+1);scanf(%d%d,&s,&d);while(s1||sG.vexnum||d1||dG.vexnum){printf(编号超出范围，重新输入);scanf(%d%d,&s,&d);}s--;d--;p=new(ArcNode);p-adjvex=d;p-nextarc=G.vertices[s].firstarc;G.vertices[s].firstarc=p;}}voidCreat_adjgraphUDG(ALGraph&G){inti,s,d;ArcNode*p,*q;G.kind=UDG;printf(请输入顶点数和边数：);scanf(%d%d,&G.vexnum,&G.arcnum);for(i=0;iG.vexnum;++i){printf(第%d个顶点信息：,i+1);scanf(%d,&G.vertices[i].data);G.vertices[i].firstarc=NULL;}for(i=0;iG.arcnum;++i){printf(第%d条边的起始顶点编号和终止顶点编号：,i+1);scanf(%d%d,&s,&d);while(s1||sG.vexnum||d1||dG.vexnum){printf(编号超出范围，重新输入);scanf(%d%d,&s,&d);}s--;d--;p=new(ArcNode);p-adjvex=d;p-nextarc=G.vertices[s].firstarc;G.vertices[s].firstarc=p;q=new(ArcNode);q-adjvex=s;q-nextarc=G.vertices[d].firstarc;G.vertices[d].firstarc=q;}}voidPRIN(ALGraph&G){inti;ArcNode*p;if(G.kind==DG||G.kind==UDG){for(i=0;iG.vexnum;++i){printf(V%d:,G.vertices[i].data);p=G.vertices[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;iG.vexnum;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=G.vertices[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,&G.kind);switch(G.kind){caseDG:Creat_adjgraphDG(G);PRIN(G);break;caseUDG:Creat_adjgraphUDG(G);PRIN(G);break;default:printf(ERROR);break;}}voidmain(){ALGraphG;Creat_adjgraph(G);printf(\n);printf(广度优先搜索遍历序列为：\n);bfs(G,1);printf(\n);}