图的深度和广度遍历(采用邻接表存储).docx

《图的深度和广度遍历(采用邻接表存储).docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、//图的深度遍历和广度遍历//采用邻接表存储#include#include#defineINFINITY100#defineMAX_VERTEX_NUM20#defineOK1#defineERROR-1typedefcharVertexType;typedefcharInfoType;typedefVertexTypeQElemType;boolvisited[MAX_VERTEX_NUM];//访问标志数组typedefstructQNode{QElemTypedata;structQNode*next

2、;}QNode,*QueuePtr;typedefstruct{QueuePtrfront;QueuePtrrear;}LinkQueue;intInitQueue(LinkQueue&Q){Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));if(!Q.front)returnERROR;Q.front->next=NULL;returnOK;}intDestroyQueue(LinkQueue&Q){while(Q.front){Q.rear=Q.front->next;free(Q.front);Q

3、.front=Q.rear;}returnOK;}//DestroyQueueintEnQueue(LinkQueue&Q,QElemTypee){QueuePtrp;//p=(QueuePtr)malloc(sizeof(QNode));if(!p)returnERROR;p->data=e;p->next=NULL;Q.rear->next=p;Q.rear=p;returnOK;}intDeQueue(LinkQueue&Q,QElemType&e){if(Q.front==Q.rear)returnERROR;QueuePtrp;p=Q.

4、front->next;e=p->data;Q.front->next=p->next;if(Q.rear==p)Q.rear=Q.front;free(p);returnOK;}intQueueEmpty(LinkQueueQ){if(Q.rear==Q.front)return1;elsereturn0;}typedefstructArcNode{intadjvex;structArcNode*nextarc;intweight;InfoType*info;}ArcNode;typedefstructVNode{VertexTypedata;

5、ArcNode*firstarc;intvexnum,arcnum;}VNode,AdjList[MAX_VERTEX_NUM];typedefstruct{AdjListvertices;intvexnum,arcnum;}ALGraph;intLocateVex(ALGraphG,VertexTypev){inti;for(i=0;i

6、inti;for(i=0;iadjvex;//返回第一个邻接点所在的位置break;}returnERROR;}intNextAdjVex(ALGraphG,VertexTypev,VertexTypew){//返回顶点所在位置inti,j;i=LocateVex(G,v);j=LocateVex(G,w);intflag=0;ArcNode*p;p=G.ver

7、tices[i].firstarc;while(p){if(p->adjvex==j){flag=1;break;}p=p->nextarc;}if(flag&&p->nextarc)returnp->nextarc->adjvex;elsereturnERROR;}/**************构造图，采用邻接表存储***********************/intCreatUDG(ALGraph&G){//构造无向图inti,j,k;VertexTypev1,v2;ArcNode*p,*q;printf("请输入顶点数和弧数：");sca

8、nf("%d%d",&G.vexnum,&G.arcnum);printf("请输入顶点（顶点之间不需要加空格）：");getchar(