1505120407_杜成虎_实验报告07

计算机科学与工程学院《算法与数据结构》实验报告(七)专业班级2015级计算机科学与技术1实验地点403机房学生学号1505120407指导教师蔡琼学生姓名杜成虎实验时间2017-05-20实验项目图的应用一实验类别基础性（）设计性（√）综合性（）其它（）实验目的及要求（1）熟练掌握图的基本存储方法；（2）熟练掌握图的深度优先和广度优先搜索方法。成绩评定表类别评分标准分值得分合计上机表现积极出勤、遵守纪律按要求完成设计任务30分程序与报告程序代码规范、功能正确报告详实完整、体现收获70分说明：评阅教师：蔡琼日期：2017年5月27日计算机科学与工程学院《算法与数据结构》实验报告2实验内容实验内容：图的两种遍历方法及对应的生成树。自己编写源程序，把图的深度优先遍历、广度优先遍历改为输出深度优先生成树、广度优先生成树。实验说明：（1）读懂教师给定的程序或课本的程序；（2）输入图；（3）把显示遍历序列改为显示深度优先、广度优先生成树。#includestdio.h#includemalloc.h#defineMAXV100#defineINF1024typedefintInfotype;typedefstruct{intno;Infotypeinfo;}Vertextype;typedefstruct{intedges[MAXV][MAXV];intn,e;Vertextypevexs[MAXV];}Mgraph;typedefstructAnode{intadjvex;structAnode*nextarc;Infotypeinfo;}Arcnode;typedefintVertex;typedefstructVNode{Vertexdata;Arcnode*firstarc;}Vnode;typedefVnodeAdjlist[MAXV];typedefstruct{Adjlistadjlist;intn,e;}Algraph;voidMattolist(Mgraphg,Algraph*&G){inti,j;Arcnode*p;G=(Algraph*)malloc(sizeof(Algraph));for(i=0;ig.n;i++)计算机科学与工程学院《算法与数据结构》实验报告3G-adjlist[i].firstarc=NULL;for(i=0;ig.n;i++)for(j=g.n-1;j=0;j--)if(g.edges[i][j]!=0){p=(Arcnode*)malloc(sizeof(Arcnode));p-adjvex=j;p-nextarc=G-adjlist[i].firstarc;G-adjlist[i].firstarc=p;}G-n=g.n;G-e=g.e;}voidDispadj(Algraph*G){inti;Arcnode*p;for(i=0;iG-n;i++){p=G-adjlist[i].firstarc;printf(%3d:,i);while(p!=NULL){printf(%3d,p-adjvex);p=p-nextarc;}printf(\n);}}intvisited[MAXV];voidDFS(Algraph*G,intv){Arcnode*p;visited[v]=1;p=G-adjlist[v].firstarc;while(p!=NULL){if(visited[p-adjvex]==0){printf(%d,%d,v,p-adjvex);DFS(G,p-adjvex);}p=p-nextarc;}}voidBFS(Algraph*G,intv)计算机科学与工程学院《算法与数据结构》实验报告4{Arcnode*p;intqueue[MAXV],front=0,rear=0;intw,i;for(i=0;iG-n;i++)visited[i]=0;visited[v]=1;rear=(rear+1)%MAXV;queue[rear]=v;while(front!=rear){front=(front+1)%MAXV;w=queue[front];p=G-adjlist[w].firstarc;while(p!=NULL){if(visited[p-adjvex]==0){printf(%d,%d,w,p-adjvex);visited[p-adjvex]=1;rear=(rear+1)%MAXV;queue[rear]=p-adjvex;}p=p-nextarc;}}printf(\n);}voidmain(){inti,j;Mgraphg;Algraph*G;intA[MAXV][11]={{0,1,1,1,0,0,0,0,0,0,0},{1,0,0,0,1,1,0,0,0,0,0},{1,0,0,1,0,1,1,0,0,0,0},{1,0,1,0,0,0,0,1,0,0,0},{0,1,0,0,0,0,0,0,0,0,0},{0,1,1,0,0,0,0,0,0,0,0},{0,0,1,0,0,0,0,1,1,1,0},{0,0,0,1,0,0,1,0,0,0,1},{0,0,0,0,0,0,1,0,0,0,0},{0,0,0,0,0,0,1,0,0,0,0},{0,0,0,0,0,0,0,1,0,0,0}};g.n=11;g.e=13;for(i=0;ig.n;i++)for(j=0;jg.n;j++)g.edges[i][j]=A[i][j];G=(Algraph*)malloc(sizeof(Algraph));Mattolist(g,G);printf(图G的邻接表:\n);Dispadj(G);计算机科学与工程学院《算法与数据结构》实验报告5printf(\n);for(i=0;ig.n;i++)visited[i]=0;printf(深度优先生成树:);DFS(G,0);printf(\n);for(i=0;ig.n;i++)visited[i]=0;printf(广度优先生成树:);BFS(G,0);printf(\n);}计算机科学与工程学院《算法与数据结构》实验报告6实验总结