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

图的深度遍历和广度遍历程序源代码如下：#includestdio.h#includestdlib.h#define MAXQSIZE 100#define MVNum 100int visited100;typedef structchar *base;int front;int rear;SqQueue;int InitQueue(SqQueue &Q) /初始化队列Q.base=new charMAXQSIZE;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.baseQ.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.baseQ.front;Q.front=(Q.front+1)%MAXQSIZE;return 1;int GetHead(SqQueue Q) /取队头元素if(Q.front!=Q.rear)return Q.baseQ.front;typedef struct /定义图char vexsMVNum;int arcsMVNumMVNum;int vexnum,arcnum;AMGraph;int LocateVex(AMGraph G,char u)int i;for(i=0;iG.vexnum;+i)if(u=G.vexsi)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.vexsi);getchar();for(i=0;iG.vexnum;+i)for(j=0;jG.vexnum;+j)G.arcsij=0;for(k=0;kG.arcnum;+k)scanf(%c%c,&v1,&v2);getchar();i=LocateVex(G,v1);j=LocateVex(G,v2);G.arcsij=1;G.arcsji=G.arcsij;return 1;void DFS(AMGraph G,int v) /深度遍历图int w; printf(%c,G.vexsv);visitedv=1;for(w=0;wG.vexnum;w+)if(G.arcsvw!=0)&(!visitedw)DFS(G,w);void DFSTraverse(AMGraph G)int v;for(v=0;vG.vexnum;+v)visitedv=0;for(v=0;vG.vexnum;+v)if(!visitedv)DFS(G,v);void BFS(AMGraph G,int v) /广度遍历int w; SqQueue Q;printf(%c,G.vexsv); /访问第v个顶点visitedv=1;InitQueue(Q); /初始化队列，置空EnQueue(Q,v); /v进队char u=GetHead(Q);while(!QueueEmpty(Q) /队列非空DeQueue(Q,u); /队头元素出队,置为ufor(w=0;wG.vexsv;w+)if(visitedw)scanf(%d,&w);visitedw=1;EnQueue(Q,w); /w进队void BFSTraverse(AMGraph G) int v;for(v=0;vG.vexnum;+v)visitedv=0;for(v=0;vG.vexnum;+v)if(!visitedv)BFS(G,v);main()AMGraph G;CreateUDN(G);printf(深度遍历结果:n);DFS