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

1、课程设计题目九：图的广度优先遍历基本要求：采用邻接表存储结构实现图的广度优先遍历。（2）对任意给定的图（顶点数和边数自定），建立它的邻接表并输出；（3）实现图的广度优先遍历*/#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("请输入顶点数和边数：");scanf("%d %d",&G.vexnum,&G.arcnum);for(i=0;i<G.vexnum;+i)printf("

4、第%d个顶点信息：",i+1);scanf("%d",&G.verticesi.data);G.verticesi.firstarc=NULL;for(i=0;i<G.arcnum;+i)printf("第%d条边的起始顶点编号和终止顶点编号：",i+1);scanf("%d %d",&s,&d);while(s<1|s>G.vexnum|d<1|d>G.vexnum)printf("编号超出范围，重新输入");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("请输入顶点数和边数：");scanf("%d %d",&G.vexnum,&G.arcnum);for(i=0;i<G.vexnum;+i)printf

6、("第%d个顶点信息：",i+1);scanf("%d",&G.verticesi.data);G.verticesi.firstarc=NULL;for(i=0;i<G.arcnum;+i)printf("第%d条边的起始顶点编号和终止顶点编号：",i+1);scanf("%d %d",&s,&d);while(s<1|s>G.vexnum|d<1|d>G.vexnum)printf("编号超出范围，重新输入");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("请根据上述提示输入图的类型：");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