图的深度遍历与广度遍历.docx

图的深度遍历和广度遍历程序源代码如下：#includestdio.h#includestdlib.h#define MAXQSIZE 100#define MVNum 100int visited[100];typedef struct{char *base;int front;int rear;}SqQueue;int InitQueue(SqQueue Q) //初始化队列{Q.base=new char[MAXQSIZE];if(!Q.base)exit(-1); //存储失败Q.front=Q.rear=0; //队列为空return 1;}int QueueEmpty(SqQueue Q) //判断队非空{if(Q.front==Q.rear)return 0;return 1;}int EnQueue(SqQueue Q,char e) //入队{if((Q.rear+1)%MAXQSIZE==Q.front) //队满return 0; Q.base[Q.rear]=e; //新元素插入队尾Q.rear=(Q.rear+1)%MAXQSIZE; //队尾指针加1return 1;}int DeQueue(SqQueue Q,char e) //出队{if(Q.front==Q.rear)return 0; //队空e=Q.base[Q.front];Q.front=(Q.front+1)%MAXQSIZE;return 1;}int GetHead(SqQueue Q) //取队头元素{if(Q.front!=Q.rear)return Q.base[Q.front];}typedef struct //定义图{char vexs[MVNum];int arcs[MVNum][MVNum];int vexnum,arcnum;}AMGraph;int LocateVex(AMGraph G,char u){int i;for(i=0;iG.vexnum;++i)if(u==G.vexs[i])return i;return -1;}int CreateUDN(AMGraph G) //创建图{int i,j,k;char v1,v2;printf(输入顶点个数和边的个数:\n);scanf(%d%d,G.vexnum,G.arcnum);getchar();printf(请输入图:\n);for(i=0;iG.vexnum;++i)scanf(%c,G.vexs[i]);getchar();for(i=0;iG.vexnum;++i)for(j=0;jG.vexnum;++j)G.arcs[i][j]=0;for(k=0;kG.arcnum;++k){scanf(%c%c,v1,v2);getchar();i=LocateVex(G,v1);j=LocateVex(G,v2);G.arcs[i][j]=1;G.arcs[j][i]=G.arcs[i][j];}return 1;}void DFS(AMGraph G,int v) //深度遍历图{int w;printf(%c,G.vexs[v]);visited[v]=1;for(w=0;wG.vexnum;w++)if((G.arcs[v][w]!=0)(!visited[w]))DFS(G,w);}void DFSTraverse(AMGraph G){int v;for(v=0;vG.vexnum;++v)visited[v]=0;for(v=0;vG.vexnum;++v)if(!visited[v])DFS(G,v);}void BFS(AMGraph G,int v) //广度遍历{int w;SqQueue Q;printf(%c,G.vexs[v]); //访问第v个顶点visited[v]=1;InitQueue(Q); //初始化队列，置空EnQueue(Q,v); //v进队char u=GetHead(Q);while(!QueueEmpty(Q)) //队列非空{DeQueue(Q,u); //队头元素出队,置为ufor(w=0;wG.vexs[v];w++)if(visited[w]){scanf(%d,w);visited[w]=1;EnQueue(Q,w); //w进队}}}void BFSTraverse(AMGraph G) {int v;for(v=0;vG.vexnum;++v)visited[v]=0;for(v=0;vG.vexnum;++v)if(!visited[v])BFS(G,v);}main(){AMGraph G;CreateUDN