数据结构实验8：图子系统

《数据结构实验8：图子系统》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、验证性实验8：图子系统班级学号BX100420姓名施程程1．实验目的（1）掌握图邻接矩阵的存储方法。（2）掌握图深度优先编历的基本思想。（3）掌握图广度优先编历的基本思想。2．实验内容（1）编写按键盘输入的数据建立图的邻接矩阵存储。（2）编写图的深度优先编历程序。（3）编写图的广度优先编历程序。（4）设计一个选择式菜单形式如下：图子系统*******************************************1-------更新邻接矩阵**2-------深度优先遍历**3-------广度优先遍历**0-

2、------退出*******************************************请选择菜单号（0--3）：3．操作举例例如对右图的操作是：建立一个有向图的邻接矩阵表示。请输入顶点数和边数（输入格式为：顶点数，边数）：5,7请输入顶点信息（顶点号）每个顶点以回车键作为结束：ABCDE请输入每条边对应的两个顶点的序号（输入格式为：i，j）：请输入第1条边的顶点序号：A,B请输入第2条边的顶点序号：A,D请输入第3条边的顶点序号：B

3、,C请输入第4条边的顶点序号：C,A请输入第5条边的顶点序号：D,B请输入第6条边的顶点序号：D,E请输入第7条边的顶点序号：E,C已建立一个图的邻矩阵存储0101000100100000100100100图子系统***********************************1-------更新邻接矩阵**2-------深度优先遍历**3-------广度优先遍历**0-------退出***********************************请选择菜单号（

4、0--3）：2深度优先遍历结点:结点A深度优先遍历结点:结点B深度优先遍历结点:结点C深度优先遍历结点:结点D深度优先遍历结点:结点E图子系统***********************************1-------更新邻接矩阵**2-------深度优先遍历**3-------广度优先遍历**0-------退出***********************************请选择菜单号（0--3)：3广度优先遍历结点:结点A广度优先遍历结点:结点B广度优先遍历结点:结点C广度优先遍

5、历结点:结点D广度优先遍历结点:结点E4．实验程序#include#defineGRAPHMAX10#defineFALSE0#defineTRUE1#defineErrorprintf#defineQueueSize30typedefstruct{charvexs[GRAPHMAX];intedges[GRAPHMAX][GRAPHMAX];intn,e;}MGraph;intvisited[10];voidCreateMGraph(MGraph*G);voidDFSTraverseM(MGraph

6、*G);voidBFSTraverseM(MGraph*G);voidDFSM(MGraph*G,inti);voidBFSM(MGraph*G,inti);typedefstruct{intfront;intrear;intcount;intdata[QueueSize];}CirQueue;voidInitQueue(CirQueue*Q){Q->front=Q->rear=0;Q->count=0;}intQueueEmpty(CirQueue*Q){returnQ->count=QueueSize;}intQu

7、eueFull(CirQueue*Q){returnQ->count==QueueSize;}voidEnQueue(CirQueue*Q,intx){if(QueueFull(Q))Error("Queueoverflow");else{Q->count++;Q->data[Q->rear]=x;Q->rear=(Q->rear+1)%QueueSize;}}intDeQueue(CirQueue*Q){inttemp;if(QueueEmpty(Q)){Error("Queueunderflow");returnN

8、ULL;}else{temp=Q->data[Q->front];Q->count--;Q->front=(Q->front+1)%QueueSize;returntemp;}}voidmain(){MGraph*G,a;charch1;inti,j,ch2;G=&a;printf("tt建立一个有向图的邻接矩阵表示"