圖的深度和廣度遍歷(采用鄰接表存儲).docx

《圖的深度和廣度遍歷(采用鄰接表存儲).docx》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在教育資源-天天文庫。

1、//圖的深度遍歷和廣度遍歷//采用鄰接表存儲#include#include#defineINFINITY100#defineMAX_VERTEX_NUM20#defineOK1#defineERROR-1typedefcharVertexType;typedefcharInfoType;typedefVertexTypeQElemType;boolvisited[MAX_VERTEX_NUM];//訪問標志數(shù)組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("請輸入頂點數(shù)和弧數(shù)：");sca

8、nf("%d%d",&G.vexnum,&G.arcnum);printf("請輸入頂點（頂點之間不需要加空格）：");getchar(