资源描述：
《数据结构实验7+1107112128+杨士岩》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、《数据结构》实验报告实验序号：7 实验项目名称：图的定义和操作学 号1107112128`姓 名杨士岩专业、班商务智能实验地点1-307指导教师谢彦麒实验时间12/5一、实验目的及要求1.熟悉图的邻接矩阵及邻接表的表示方法。2.掌握建立图的邻接矩阵算法，并由邻接矩阵转化为邻接表3.熟悉对图遍历算法。二、实验设备（环境）及要求微型计算机；windows操作系统；MicrosoftVisualStudio6.0集成开发环境。三、实验内容与步骤1．试着找出图G的最小生成树，画出它的最小生成树。如下图所示：
2、2.定义无向图邻接矩阵如下：typedefstructgraph{vextypevexs[n];//顶点adjtypearcs[n][n];//边};改写以上程序，实现功能如下(任选二题)：1.已知邻接矩阵，将其转化为邻接表表示。typedefstructnode{intadjvex;//顶点structnode*next;//指向下一条边}edgenode;2.判断邻接矩阵或邻接表的是否连通；3.对邻接矩阵或邻接表进行深度优先和广度优先遍历；4．判断邻接矩阵或邻接表任意两点之间是否有连通；5．生成邻接矩阵或邻接表的最小
3、生成树。四、实验结果与数据处理详细记录程序在调试过程中出现的问题及解决方法。记录程序执行的结果（贴图）。五、分析与讨论对上机实践结果进行分析，上机的心得体会。六、教师评语签名：日期：成绩附源程序清单：对邻接矩阵进行深度优先和广度优先遍历；#defineM20#include#include#include/*定义图*/typedefstruct{intV[M];intR[M][M];intvexnum;}Graph;/*创建图*/voidcreatgraph(Gr
4、aph*g,intn){inti,j,r1,r2;g->vexnum=n;/*顶点用i表示*/for(i=1;i<=n;i++){g->V[i]=i;}/*初始化R*/for(i=1;i<=n;i++)for(j=1;j<=n;j++){g->R[i][j]=0;}/*输入R*/printf("请输入坐标(r1,r2)：(输入(0,0)结束输入)");scanf("%d,%d",&r1,&r2);while(r1!=0&&r2!=0){g->R[r1][r2]=1;g->R[r2][r1]=1;scanf("%d,%
5、d",&r1,&r2);}}/*打印图的邻接矩阵*/voidprintgraph(Graph*g){inti,j;for(i=1;i<=g->vexnum;i++){for(j=1;j<=g->vexnum;j++){printf("%2d",g->R[i][j]);}printf("");}}/*全局变量：访问标志数组*/intvisited[M];/*访问顶点*/voidvisitvex(Graph*g,intvex){printf("%d",g->V[vex]);}/*获取第一个未被访问的邻接节点*/intfi
6、rstadjvex(Graph*g,intvex){intw,i;for(i=1;i<=g->vexnum;i++){if(g->R[vex][i]==1&&visited[i]==0){w=i;break;}else{w=0;}}returnw;}/*获取下一个未被访问的邻接节点(深度遍历)*/intnextadjvex(Graph*g,intvex,intw){intt;t=firstadjvex(g,w);returnt;}/*深度递归遍历*/voiddfs(Graph*g,intvex){intw;visited
7、[vex]=1;visitvex(g,vex);for(w=firstadjvex(g,vex);w>0;w=nextadjvex(g,vex,w))if(!visited[w]){dfs(g,w);}}voiddfstraverse(Graph*g){inti;for(i=1;i<=g->vexnum;i++)visited[i]=0;for(i=1;i<=g->vexnum;i++)if(!visited[i]){dfs(g,i);}}/*定义队列*/typedefstruct{intV[M];intfront;in
8、trear;}Queue;/*初始化队列*/initqueue(Queue*q){q->front=0;q->rear=0;}/*判断队列是否为空*/intquempty(Queue*q){if(q->front==q->rear){return0;}else{return1;}}/*入队操作*/enqueue(Qu
