搜索
//图的深度遍历和广度遍历//采用邻接表存储#includestdio.h#includestdlib.h#defineINFINITY100#defineMAX_VERTEX_NUM20#defineOK1#defineERROR-1typedefcharVertexType;typedefcharInfoType;typedefVertexTypeQElemType;boolvisited[MAX_VERTEX_NUM];//访问标志数组typedefstructQNode{QElemTypedata;structQNode*next;}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.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.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;ArcNode*firstarc;intvexnum,arcnum;}VNode,AdjList[MAX_VERTEX_NUM];typedefstruct{AdjListvertices;intvexnum,arcnum;}ALGraph;intLocateVex(ALGraphG,VertexTypev){inti;for(i=0;iG.vexnum;i++){if(G.vertices[i].data==v)returni;}returnOK;}intFirstAdjVex(ALGraphG,VertexTypev){//返回顶点所在位置inti;for(i=0;iG.vexnum;i++)if(v==G.vertices[i].data&&G.vertices[i].firstarc){returnG.vertices[i].firstarc-adjvex;//返回第一个邻接点所在的位置break;}returnERROR;}intNextAdjVex(ALGraphG,VertexTypev,VertexTypew){//返回顶点所在位置inti,j;i=LocateVex(G,v);j=LocateVex(G,w);intflag=0;ArcNode*p;p=G.vertices[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(请输入顶点数和弧数：);scanf(%d%d,&G.vexnum,&G.arcnum);printf(请输入顶点（顶点之间不需要加空格）：);getchar();//吃掉多余的回车键，for(i=0;iG.vexnum;i++){scanf(%c,&G.vertices[i].data);G.vertices[i].firstarc=NULL;//初始化firstarc指针}getchar();for(k=0;kG.arcnum;++k){printf(请输入v1和v2:);scanf(%c%c,&v1,&v2);getchar();//printf(请输入权值w:);scanf(%d,&w);getchar();i=LocateVex(G,v1);j=LocateVex(G,v2);//确定v1和v2在G中位置p=(ArcNode*)malloc(sizeof(ArcNode));q=(ArcNode*)malloc(sizeof(ArcNode));p-nextarc=G.vertices[i].firstarc;q-nextarc=G.vertices[j].firstarc;G.vertices[i].firstarc=p;p-adjvex=j;G.vertices[j].firstarc=q;q-adjvex=i;//if(IncInfo)scanf(G.arcs[i][j].info);//输入弧含有相关信息}return0;}/****************图的深度遍历*****************/voidDFS(ALGraphG,inti){//从第i个顶点出发递归地深度优先遍历图G。intj;visited[i]=true;printf(%c,G.vertices[i].data);//访问第i个顶点for(j=FirstAdjVex(G,G.vertices[i].data);j!=ERROR;j=NextAdjVex(G,G.vertices[i].data,G.vertices[j].data))//if(!visited[j])DFS(G,j);//对尚未访问的邻接顶点递归调用DFS}voidDFSTraverse(ALGraphG){//对图G作深度优先遍历。inti;for(i=0;iG.vexnum;++i)visited[i]=false;//访问标志数组初始化for(i=0;iG.vexnum;++i)if(!visited[i])DFS(G,i);//对尚未访问的顶点调用DFS}/*********************图的广度遍历***********************/voidBFSTraverse(ALGraphG){//按广度优先非递归遍历图G。使用辅助队列Q和访问标志数组visited。inti,j;VertexTypeu;LinkQueueQ;InitQueue(Q);//置空的辅助队列Qfor(i=0;iG.vexnum;++i)visited[i]=false;for(i=0;iG.vexnum;++i)if(!visited[i]){//i尚未访问visited[i]=true;printf(%c,G.vertices[i].data);//访问第i个顶点//访问EnQueue(Q,G.vertices[i].data);//顶点入队列while(!QueueEmpty(Q)){DeQueue(Q,u);//队头元素出队并置为ufor(j=FirstAdjVex(G,u);j!=ERROR;j=NextAdjVex(G,u,G.vertices[j].data))if(!visited[j]){//u的尚未访问的邻接顶点j入队列Qvisited[j]=true;printf(%c,G.vertices[j].data);//访问第j个顶点EnQueue(Q,G.vertices[j].data);}//if}//while}//if}//BFSTraverseintmain(){ALGraphG;CreatUDG(G);printf(深度遍历结果为：);DFSTraverse(G);printf(\n);printf(广度遍历结果为：);BFSTraverse(G);printf(\n);return0;}