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

《建立图地邻接矩阵或邻接表存储并在此基础上实现图地深度优先遍历和广度优先遍历》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、#include"stdafx.h"#include"conio.h"#include"stdio.h"#include"stdlib.h"typedefenum{FALSE,TRUE}BOOLEAN;#defineOVERFLOW-1#defineOK1#defineERROR0#defineINFINITYINT_MAX/*最大值∞*//*根据图的权值类型，分别定义为最大整数或实数*/#defineMAX_VERTEX_NUM20/*最大顶点数目*/typedefenum{DG,DN,UDG,UDN

2、}GraphKind;/*{有向图，有向网，无向图，无向网}*/BOOLEANVisited[MAX_VERTEX_NUM];BOOLEANvisited[MAX_VERTEX_NUM];#defineVEX_NUM20#defineMAXSIZE50typedefcharVextype;typedefintElemType;typedefintStatus;//////////////////////////////邻接矩阵结构定义typedefstruct{Vextypevexs[VEX_NUM];

3、intadj[VEX_NUM][VEX_NUM];/*邻接矩阵*/intn,e;/*顶点数和边数*/}Mgraph;//////////////////////////////邻接表结构定义typedefstructnode{/*边结点*/intadjvex;/*邻接点域*/structnode*nextarc;/*指向下一个边结点的指针域*/}EdgeNode;typedefstructvnode{//顶点结构，2个域，结点信息和第一个邻接点Vextypevertex;EdgeNode*firsted

4、ge;}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中寻找

5、第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;//cha

6、rch;printf("请输入顶点数和边数:");scanf("%d,%d",&(G->n),&(G->e));/*输入*/printf("请输入顶点信息:");for(i=0;in;i++)scanf("%s",&(G->vexs[i]));for(i=0;in;i++)for(j=0;jn;j++)G->adj[i][j]=0;/*初始化邻接矩阵*/printf("输入每条边对应的两个顶点的序号:");for(k=0;ke;k++){scanf("%d,%

7、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("请输入顶点数和边数:");scanf("%d,%d",&(G->n),&(G->e));printf("请输入顶点信息Vi例如a，每输入一个顶点后回车:");fo

8、r(i=0;in;i++){scanf("%s",&vi);G->adjlist[i].vertex=vi;G->adjlist[i].firstedge=NULL;}printf("顶点:");for(i=0;in;i++)printf("%c(%d)-",G->adjlist[i].vertex,i+1);printf("请输入边的信息(vi,vj)例如:1,2:");for(k=0;ke;k++){