建立图的邻接矩阵或邻接表存储并在此基础上实现图的深度优先遍历和广度优先遍历

#includestdafx.h#includeconio.h#includestdio.h#includestdlib.htypedefenum{FALSE,TRUE}BOOLEAN;#defineOVERFLOW-1#defineOK1#defineERROR0#defineINFINITYINT_MAX/*最大值∞*//*根据图的权值类型，分别定义为最大整数或实数*/#defineMAX_VERTEX_NUM20/*最大顶点数目*/typedefenum{DG,DN,UDG,UDN}GraphKind;/*{有向图，有向网，无向图，无向网}*/BOOLEANVisited[MAX_VERTEX_NUM];BOOLEANvisited[MAX_VERTEX_NUM];#defineVEX_NUM20#defineMAXSIZE50typedefcharVextype;typedefintElemType;typedefintStatus;//////////////////////////////邻接矩阵结构定义typedefstruct{Vextypevexs[VEX_NUM];intadj[VEX_NUM][VEX_NUM];/*邻接矩阵*/intn,e;/*顶点数和边数*/}Mgraph;//////////////////////////////邻接表结构定义typedefstructnode{/*边结点*/intadjvex;/*邻接点域*/structnode*nextarc;/*指向下一个边结点的指针域*/}EdgeNode;typedefstructvnode{//顶点结构，2个域，结点信息和第一个邻接点Vextypevertex;EdgeNode*firstedge;}VertexNode;typedefstruct{//图结构VertexNodeadjlist[MAXSIZE];intn,e;}ALGraph;////intFirstAdjVex(ALGraphG,intv){//在图G中寻找第v个顶点的第一个邻接顶点if(!G.adjlist[v].firstedge)return-1;elsereturn(G.adjlist[v].firstedge-adjvex);}intNextAdjVex(ALGraphG,intv,intw){//在图G中寻找第v个顶点的相对于w的下一个邻接顶点EdgeNode*p;intvi;p=G.adjlist[v].firstedge;if(!p)return-1;while(p-adjvex!=w)p=p-nextarc;//在顶点v的弧链中找到顶点wp=p-nextarc;if(!p)return-1;//若已是最后一个顶点，返回-1else{vi=p-adjvex;returnvi;//返回下一个邻接顶点的序号}}////voidCreateMGraph(Mgraph*G){inti,j,k;//charch;printf(请输入顶点数和边数:\n);scanf(%d,%d,&(G-n),&(G-e));/*输入*/printf(请输入顶点信息:\n);for(i=0;iG-n;i++)scanf(%s,&(G-vexs[i]));for(i=0;iG-n;i++)for(j=0;jG-n;j++)G-adj[i][j]=0;/*初始化邻接矩阵*/printf(输入每条边对应的两个顶点的序号:\n);for(k=0;kG-e;k++){scanf(%d,%d,&i,&j);/*输入e条边*/G-adj[i][j]=1;G-adj[j][i]=1;/*对称加入,无向图的邻接矩阵存储建立*/}}/*CreateMGraph*/voidCreateALGraph(ALGraph*G){/*建立无向图的邻接表存储*/inti,j,k;charvi;EdgeNode*s;printf(请输入顶点数和边数:\n);scanf(%d,%d,&(G-n),&(G-e));printf(请输入顶点信息Vi\n例如a，每输入一个顶点后回车:\n);for(i=0;iG-n;i++){scanf(%s,&vi);G-adjlist[i].vertex=vi;G-adjlist[i].firstedge=NULL;}printf(顶点:);for(i=0;iG-n;i++)printf(%c(%d)-,G-adjlist[i].vertex,i+1);printf(\n请输入边的信息(vi,vj)\n例如:1,2:\n);for(k=0;kG-e;k++){/*建立边表*/scanf(%d,%d,&i,&j);//在头结点和边结点之间插入新的边结点s=(EdgeNode*)malloc(sizeof(EdgeNode));s-adjvex=j-1;s-nextarc=G-adjlist[i-1].firstedge;G-adjlist[i-1].firstedge=s;s=(EdgeNode*)malloc(sizeof(EdgeNode));s-adjvex=i-1;s-nextarc=G-adjlist[j-1].firstedge;G-adjlist[j-1].firstedge=s;}////输出邻接表...}/*CreateALGraph*/voidDFS(ALGraph*G,intv){EdgeNode*p;Visited[v]=TRUE;printf(%c-,G-adjlist[v].vertex);/*置访问标志，访问顶点v*/p=G-adjlist[v].firstedge;/*链表的第一个结点*/while(p!=NULL){if(!Visited[p-adjvex])DFS(G,p-adjvex);/*从v的未访问过的邻接顶点出发深度优先搜索*/p=p-nextarc;}}voidDFS_traverse(ALGraph*G){intv;EdgeNode*p;printf(深度度优先搜索输出结点信息:);for(v=0;vG-n;v++)Visited[v]=FALSE;/*访问标志初始化*/p=G-adjlist[v].firstedge;for(v=0;vG-n;v++)if(!Visited[v])DFS(G,v);}///////////////队列///////////////////////typedefstructNode{ElemTypedata;//元素数据structNode*next;//链式队列中结点元素的指针}QNode,*QueuePtr;typedefstruct{QueuePtrfront;//队列头指针QueuePtrrear;//队列尾指针}LinkQueue;StatusInitQueue(LinkQueue&Q){//构造一个空队列QQ.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));if(Q.front==NULL)exit(OVERFLOW);//存储失败Q.front-next=NULL;returnOK;}StatusDestoryQueue(LinkQueue&Q){//销毁队列Qwhile(Q.front){Q.rear=Q.front-next;//利用尾指针移动保存队头指针free(Q.front);//依次释放头结点Q.front=Q.rear;}returnOK;}StatusQueueEmpty(LinkQueueQ){//assert(Q.front!=NULL&&Q.rear!=NULL);if(Q.front==Q.rear)returnTRUE;elsereturnFALSE;}StatusEnQueue(LinkQueue&Q,ElemTypee)//插入元素e为Q新的队尾元素{QueuePtrp=(QueuePtr)malloc(sizeof(QNode));if(!p)exit(OVERFLOW);//存储失败p-data=e;p-next=NULL;Q.rear-next=p;//当前队尾指针指向新的结点Q.rear=p;//移动队尾知道到新的结点，当前结点成为队尾结点returnOK;}StatusDeQueue(LinkQueue&Q,ElemType*e)//若队列不空，则删除Q的队头元素，用e返回值，并返回OK。否则返回ERROR{if(Q.front==Q.rear)returnERROR;QueuePtrp=Q.front-next;*e=p-data;Q.front-next=p-next;if(Q.rear==p)Q.rear=Q.front;//只有一个元素，恢复到空队列，只有各头结点free(p);returnOK;}///////////////////////////////////////intVisit(intv,ALGraphG){//printf(%d,v);printf(%c-,G.adjlist[v].vertex);returnOK;}voidBFSTraverse(ALGraphG,Status(*Visit)(intv,ALGraphG)){//连通图G广度优先搜索LinkQueueQ;ElemTypeu;//EdgeNode*p;intv;intw;printf(广度优先搜索输出结点信息:);for(v=0;vG.n;++v)visited[v]=FALSE;//初始化访问标志InitQueue(Q);//置空的辅助队列for(v=0;vG.n;++v)if(!visited[v]){//v未访问visited[v]=TRUE;Visit(v,G);EnQueue(Q,v);//v入队列while(!QueueEmpty(Q)){DeQueue(Q,&u);//队头元素出队并置为ufor(w=FirstAdjVex(G,u);w=0;w=NextAdjVex(G,u,w))if(!visited[w]){//w为u尚未访问的邻接顶点visited[w]=TRUE;Visit(w,G);EnQueue(Q,w);//访问的顶点w入队列}//if}//while}//if}//BFSTraversevoidmain(){//MgraphGm;//CreateMGraph(&Gm);//邻接矩阵存储ALGraphG2;//邻接表存储do{CreateALGraph(&G2);DFS_traverse(&G2);printf(\n==============\n);BFSTraverse(G2,Visit);printf(\n=====是否还继续?0-退出====\n);}while(getch()!='0');}