BX100436周玲实验8：图子系统

验证性实验8：图子系统班级学号BX100436姓名周玲成绩1．实验目的（1）掌握图邻接矩阵的存储方法。（2）掌握图深度优先编历的基本思想。（3）掌握图广度优先编历的基本思想。2．实验内容（1）编写按键盘输入的数据建立图的邻接矩阵存储。（2）编写图的深度优先编历程序。（3）编写图的广度优先编历程序。（4）设计一个选择式菜单形式如下：图子系统*******************************************1-------更新邻接矩阵 **2-------深度优先遍历 **3-------广度优先遍历 **0-------退出 *******************************************请选择菜单号（0--3）：3．操作举例例如对右图的操作是：建立一个有向图的邻接矩阵表示。请输入顶点数和边数（输入格式为：顶点数，边数）：5,7<CR>请输入顶点信息（顶点号<CR>）每个顶点以回车键作为结束：A<CR>B<CR>C<CR>D<CR>E<CR>请输入每条边对应的两个顶点的序号（输入格式为：i，j）：请输入第1条边的顶点序号：A,B<CR>请输入第2条边的顶点序号：A,D<CR>请输入第3条边的顶点序号：B,C<CR>请输入第4条边的顶点序号：C,A<CR>请输入第5条边的顶点序号：D,B<CR>请输入第6条边的顶点序号：D,E<CR>请输入第7条边的顶点序号：E,C<CR>已建立一个图的邻矩阵存储0101000100100000100100100图子系统***********************************1-------更新邻接矩阵**2-------深度优先遍历**3-------广度优先遍历**0-------退出***********************************请选择菜单号（0--3）：2<CR>深度优先遍历结点:结点A深度优先遍历结点:结点B深度优先遍历结点:结点C深度优先遍历结点:结点D深度优先遍历结点:结点E图子系统***********************************1-------更新邻接矩阵**2-------深度优先遍历**3-------广度优先遍历**0-------退出***********************************请选择菜单号（0--3)：3<CR>广度优先遍历结点:结点A广度优先遍历结点:结点B广度优先遍历结点:结点C广度优先遍历结点:结点D广度优先遍历结点:结点E4．实验程序#include<stdio.h>#defineGRAPHMAX10#defineFALSE0#defineTRUE1#defineErrorprintf#defineQueueSize30typedefstruct{ charvexs[GRAPHMAX]; intedges[GRAPHMAX][GRAPHMAX]; intn,e;}MGraph;intvisited[10];voidCreateMGraph(MGraph*G);voidDFSTraverseM(MGraph*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;}intQueueFull(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");returnNULL; } 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("\n\t\t建立一个有向图的邻接矩阵表示\n"); CreateMGraph(G); printf("\n\t\t已建立一个图的邻矩阵存储\n"); for(i=0;i<G->n;i++) { printf("\n\t\t"); for(j=0;j<G->n;j++) printf("%5d",G->edges[i][j]); } getchar(); ch1='y'; while(ch1=='y'||ch1=='Y') { printf("\n"); printf("\n\t\t图子系统"); printf("\n\t\t******************************************"); printf("\n\t\t*1-------更新邻接矩阵 *"); printf("\n\t\t*2-------深度优先遍历 *"); printf("\n\t\t*3-------广度优先遍历 *"); printf("\n\t\t*0-------退出 *"); printf("\n\t\t******************************************"); printf("\n\t\t请选择菜单号（0--3）："); scanf("%d",&ch2); getchar(); switch(ch2) { case1:CreateMGraph(G); printf("\n\t\t图的邻接矩阵存储建立完毕。");break; case2:DFSTraverseM(G);break; case3:BFSTraverseM(G);break; case0:ch1='n';break; default:printf("\n\t\t输入错误！请重新输入！"); } }}voidCreateMGraph(MGraph*G){ inti,j,k; charch1,ch2; printf("\n\t\t请输入顶点数，边数并按【Enter】键（格式如：3,4）："); scanf("%d,%d",&(G->n),&(G->e)); for(i=0;i<G->n;i++) { getchar(); printf("\n\t\t请输入第%d个顶点并按回车：",i+1); scanf("%c",&(G->vexs[i])); } for(i=0;i<G->n;i++) for(j=0;j<G->n;j++) G->edges[i][j]=0; for(k=0;k<G->e;k++) { getchar(); printf("\n\t\t请输入第%d条边的顶点序号（格式为：i,j）：",k+1); scanf("%c,%c",&ch1,&ch2); for(i=0;ch1!=G->vexs[i];i++); for(j=0;ch2!=G->vexs[j];j++); G->edges[i][j]=1; }}voidDFSTraverseM(MGraph*G){ inti; for(i=0;i<G->n;i++) visited[i]=FALSE; for(i=0;i<G->n;i++) if(!visited[i]) DFSM(G,i);}voidBFSTraverseM(MGraph*G){ inti; for(i=0;i<G->n;i++) visited[i]=FALSE; for(i=0;i<=G->n;i++) if(!visited[i]) BFSM(G,i);}voidDFSM(MGraph*G,inti){ intj; printf("\n\t\t生深度优先遍历序列：%c\n",G->vexs[i]); visited[i]=TRUE; for(j=0;j<G->n;j++) if(G->edges[i][j]==1&&!visited[j]) DFSM(G,j);}voidBFSM(MGraph*G,intk){ inti,j; CirQueueQ; InitQueue(&Q); printf("\n\t\t广度优先遍历序列：%c\n",G->vexs[k]); visited[k]=(&Q,k); while(!QueueEmpty(&Q)) { i=DeQueue(&Q); for(j=0;j<G->n;j++) if(G->edges[i][j]==1&&!visited[j]) { visited[j]=TRUE;EnQueue(&Q,j); } }}5．运行结果(1)首先是建立一个有向图的邻接矩阵，输入顶点数，5和边数，7，然后输入每条边对应的两个顶点的序号。（2）输入2，输出深度优先遍历序列。（3）输入3，输出广度优先遍历序列。（4）输入1，更新邻接矩阵。（5）输入0，退出。6．实验小结通过第八章《图》的学习以及本次验证性实验，加深了我对图的理解。图是一种重要的非线性结构，它是由顶点和集合和顶点间边的集合组成，所以它的存储也包括顶点信息和边的信息。我个人觉得本章要掌握的知识点比较多，一些专业名词比较多，生涩难理解，必须在课下花时间去看书