无向图建立、深度优先遍历和广度优先遍历实现算法

数据结构中关于无向图建立、深度优先遍历和广度优先遍历实现算法2011-03-1614:29#include#includeusingnamespacestd;#defineMaxVertexNum100typedefcharVertexType;typedefintEdgeType;typedefintDatatype;typedefstructVertexTypevexsMaxVertexNum;EdgeTypeedgeMaxVertexNumMaxVertexNum;intn,e;MGragh;typedefstructqueuenodeDatatypedata;structqueuenode*next;QueueNode;typedefstructQueueNode*front;QueueNode*rear;LinkQueue;voidInitQueue(LinkQueue*Q)Q-front=Q-rear=NULL;intQueueEmpty(LinkQueue*Q)returnQ-front=NULL&Q-rear=NULL;voidEnQueue(LinkQueue*Q,Datatypex)QueueNode*p=(QueueNode*)malloc(sizeof(QueueNode);p-data=x;p-next=NULL;if(QueueEmpty(Q)Q-front=Q-rear=p;elseQ-rear-next=p;Q-rear=p;DatatypeDeQueue(LinkQueue*Q)Datatypex;QueueNode*p;if(QueueEmpty(Q)printf(QueueEmpty);p=Q-front;x=p-data;Q-front=p-next;if(Q-rear=p)Q-rear=NULL;free(p);returnx;intvisitedMaxVertexNum;voidDFS(MGragh*G,inti);MGragh*CreateMGraph(MGragh*G)inti,j,k,w;*G=(MGragh*)malloc(sizeof(MGragh);printf(请输入顶点数和边数:)；scanf(%d%d,&(*G)-n),&(*G)-e);fflush(stdin);printf(请输入顶点值：(中间不要有空格如：ABCDEF)n);for(i=0;in;i+)(*G)-vexsi=getchar();for(i=0;in;i+)for(j=0;jn;j+)(*G)-edgeij=0;fflush(stdin);printf(请输入(Vi,Vj)上的权w:n);for(k=0;ke;k+)scanf(%d%d%d,&i,&j,&w);(*G)-edgeij=w;(*G)-edgeji=w;return*G;voidDisMGraph(MGragh*G)inti,j;for(i=0;in;i+)printf(t);for(j=0;jn;j+)printf(%dt,G-edgeij);printf(n);voidDFSTraverse(MGragh*G,intk)/深度优先遍历inti;for(i=0;in;i+)visitedi=0;DFS(G,k);for(i=0;in;i+)if(!visitedi)DFS(G,i);voidDFS(MGragh*G,inti)coutvisitvertex:vexsiendl;visitedi=1;for(intj=0;jn;j+)if(G-edgeij&!visitedj)DFS(G,j);voidBFS(MGragh*G,intk)inti,j,t;LinkQueueQ;InitQueue(&Q);for(t=0;tn;t+)visitedt=0;printf(visitvertex:%cn,G-vexsk);visitedk=1;EnQueue(&Q,k);while(!QueueEmpty(&Q)i=DeQueue(&Q);for(j=0;jn;j+)if(G-edgeij&!visitedj)printf(visitvertex:%cn,G-vexsj);visitedj=1;EnQueue(&Q,j);voidmain()MGragh*G=NULL,*P=NULL;inti;P=CreateMGraph(&G);DisMGraph(P);printf(请输入要遍历的顶点编号：)；scanf(%d,&i);printf(深度优先遍历顺序是:n);DFSTraverse(P,i);printf(广度优先遍历顺序是:n);BFS(P,i);