数据结构实验6

《数据结构实验6》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、实验六：图及其应用实验一、实验目的1.掌握图的含义；2.掌握用邻接矩诒和邻接表的方法描述图的存储结构3.理解并掌握图的二种遍历方式及相应算法；4.掌握最小生成树的冇关算法；5.理解拓扑排序的思路与算法。二、基本原理1、图的邻接矩阵、邻接矩阵存储方法描述v请自己认真书写完成＞2、图的两种遍历算法的基本思想描述v请自己认真书写完成＞3、prim算法的基本思想描述v请自己认真书写完成〉三、实验内容1、编程实现：（1）按键盘输入的数据建立图的邻接矩阵存储；（2）图的深度优先编历程序；（3）图的广度优先编历程序；（4）设计一个选择式菜单

2、形式如卜•：图子系统kwrprj%rj^♦卜rjw*prj*•卜rj%rj*•卜rjwrj%rj^rj%rj^rf%rj^rf%rprf%rprjwrj^ry*rf%rj^rf%rp*1——更新邻接矩阵**2深度优先遍历**3——广度优先遍历**0退出*vixvl＞kLxkL^■匕kL^*7*rp夕卜*7*rprj%rj*rprj%rj、rprj*rprprj*rprj*rp*7**7*rprj**7*rp［操作举例］（1）按下图建立图的邻接矩阵存储;（2）按提示输入：建立一个有向图的邻接矩阵表示请输入顶点数和边数（输入格式为

3、:顶点数，边数）：5,7vCR>请输入顶点信息（顶点号BvCR>CvCR>DvCR>EvCR>请输入每条边对应的两个顶点的序号（输入格式为:i,j）：请输入第1条边的顶点序号：A,BvCR>请输入第2条边的顶点序号：A,DvCR>请输入第3条边的顶点序号：B,CvCR>请输入笫4条边的顶点序号：C,AvCR>请输入笫5条边的顶点序号：D,BvCR>请输入第6条边的顶点序号：D,EvCR>请输入第7条边的顶点序号：E,CvCR>已建立一个图的邻短阵存储100000010001000110

4、0010001（3）再进行图的其它操作。［程序模板］#defineMAXLEN1()#includc#defineFALSE0#defineTRUE1#defineErrorprintf#dcfincQucucSizc30typedefstruct{charvexslMAXLENJ;intedges[MAXLEN][MAXLEN];intn,c;JMGraph;intvisited!10];voidCreateMGraph(MGraph*G);voidDFSTravcrscM(MGraph*G);voidBF

5、STraverseM(MGraph*G);voidDFSM(MGraph*G,inti);voidBFSM(MGraph*G,inti);typedefstruct{intfront;intrear;intcount;intdatafQueueSizel;JCirQucuc;voidInitQueue(CirQueue*Q){Q・>front=Q->rear=();Q->count=0;}intQueueEmpty(CirQueue*Q){returnQ->count=QucucSizc;}intQueueFull(Cii*Q

6、ueue*Q){rctumQ->count==QucucSizc;}voidEnQueue(CirQueue*Q,intx){if(QucucFull(Q))Error("QueueoverflowH);elseQ->count++;Q->data[Q->rear]=x;Q->rear=(Q->rear+1)%QueueSize;}}intDeQueue(CirQueue*Q){inttemp;if(QueueEmpty(Q)){Error(HQucucunderflow1*);returnNULL;)else{temp=Q-

7、>data[Q->front];Q->count~;Q->front=(Q->front+l)%QueueSize;returntemp;voidCreateMGraph(MGraph*G){inti,j,k;charchl,ch2;printf(Htt请输入顶点数和边数(格式为：顶点数，边数)：ttu);scanf(M%d,%d",&(G->n),&(G->e));printfC'XtXt请输入顶点信息(顶点号《CR》海个顶点以冋车作为结束：”);for(i=0;in;i++){getchar();p

8、rintf("tt");scanf("%c",&(G->vexs[i]));}for(i=0;in;i++)for(j=0;jn;j++)G->edges[i]

9、j]=O;printf(Mtt请输入每条边対应的两个顶点的序号数(格式为：i,j)：”