图的两种存储和遍历

《图的两种存储和遍历》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、.实验7图的两种存储和遍历一、实验内容：（1）键盘输入数据，分别建立一个有向图和一个无向图的邻接表。（2）输出该邻接表。（3）在有向图的邻接表的基础上计算各顶点的度，并输出。（4）采用邻接表存储实现无向图的深度优先遍历。（5）采用邻接表存储实现无向图的广度优先遍历。（6）在主函数中设计一个简单的菜单，分别调试上述算法。二、源代码：#include#include#include#defineMAX_VERTEX_NUM20#defineOK1#defineERROR0#define

2、OVERFLOW0intvisited[MAX_VERTEX_NUM];//表结点typedefstructArcNode{intadjvex;structArcNode*nextarc;char*info;}ArcNode;//头结点typedefstructVNode{chardata;ArcNode*firstarc;}VNode,AdjList[MAX_VERTEX_NUM];//图结构typedefstruct{word范文.AdjListvertices;intvexnum,arcnum;}ALGraph;//用于BFS遍历

3、的附设链队列结点结构typedefstructQNode{intdata;structQNode*next;}QNode,*QueuePtr;//链队列typedefstruct{QueuePtrfront;QueuePtrrear;}LinkQueue;//初始化链队intInitQueue(LinkQueue&Q){Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));if(!Q.front)exit(OVERFLOW);Q.front->next=NULL;returnOK;}//元素e入队

4、intEnQueue(LinkQueue&Q,inte){QueuePtrp;p=(QueuePtr)malloc(sizeof(QNode));if(!p)exit(OVERFLOW);p->next=NULL;p->data=e;Q.rear->next=p;Q.rear=p;returnOK;}//队首元素出队,由e返回其值intDeQueue(LinkQueue&Q,int&e){QueuePtrp;if(Q.front==Q.rear)exit(OVERFLOW);p=Q.front->next;e=p->data;Q.fro

5、nt->next=p->next;if(Q.rear==p)word范文.Q.rear=Q.front;free(p);returnOK;}//判断队列Q是否为空intEmptyQueue(LinkQueueQ){if(Q.front==Q.rear)return1;return0;}//查找值为v的顶点在顶点向量G.vexs[]中的位置intLocateVex(ALGraphG,charv){inti;for(i=0;i

6、/返回v的第一个邻接顶点的序号intFirstAdjVex(ALGraphG,charv){inti;ArcNode*p;i=LocateVex(G,v);if(i==-1)return-1;p=G.vertices[i].firstarc;if(p)returnp->adjvex;elsereturn-1;}//返回v的(相对于w)的下一个邻接顶点的序号intNextAdjVex(ALGraphG,charv,charw){inti,j;ArcNode*p,*q;i=LocateVex(G,v);j=LocateVex(G,w);if

7、(i==-1

8、

9、j==-1

10、

11、i==j)return-1;p=G.vertices[i].firstarc;while(p->nextarc&&p->adjvex!=j)word范文.p=p->nextarc;if(p->nextarc){q=p->nextarc;returnq->adjvex;}elsereturn-1;}//采用邻接表表示，构造有向图GintCreateDG(ALGraph&G){intv,e,i,j,t;ArcNode*p,*q;chartail,head;printf("输入顶点个数:");scanf("%d"

12、,&v);if(v<0)returnERROR;G.vexnum=v;printf("输入弧的条数:");scanf("%d",&e);if(e<0)returnERROR;G.arcnum=e;print