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

课程设计题目九：图的广度优先遍历基本要求：采用邻接表存储结构实现图的广度优先遍历。（2）对任意给定的图（顶点数和边数自定），建立它的邻接表并输出；（3）实现图的广度优先遍历*/#include#include#include#define MAX_NUM 20int visitedMAX_NUM=0;typedef int VertexType;typedef enum DG=1,UDGGraphKind;typedef struct ArcNodeint adjvex;int weight;struct 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_adjgraphDG(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;iG.vexnum;+i)printf(第%d个顶点信息：,i+1);scanf(%d,&G.verticesi.data);G.verticesi.firstarc=NULL;for(i=0;iG.arcnum;+i)printf(第%d条边的起始顶点编号和终止顶点编号：,i+1);scanf(%d %d,&s,&d);while(sG.vexnum|dG.vexnum)printf(编号超出范围，重新输入);scanf(%d%d,&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;iG.vexnum;+i)printf(第%d个顶点信息：,i+1);scanf(%d,&G.verticesi.data);G.verticesi.firstarc=NULL;for(i=0;iG.arcnum;+i)printf(第%d条边的起始顶点编号和终止顶点编号：,i+1);scanf(%d %d,&s,&d);while(sG.vexnum|dG.vexnum)printf(编号超出范围，重新输入);scanf(%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;iadjvex+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;iadjvex=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: