29实验4创建一个图并输出图的深度优先和广度优先遍历结果

实验报告课程名称数据结构实验项目创建一个图并输出图的深度优先和广度优先遍历结果系别____计算机学院_______专业______班级/学号_学生姓名________实验日期_成绩_______________________指导教师实验题目：实验四------创建一个图并输出图的深度优先和广度优先遍历结果一、实验目的1)掌握图的存储结构；2)掌握并实现图的深度优先和广度优先遍历算法；3)理解图的应用，包括最小生成树、拓扑排序、关键路径、最短路径；二、实验内容1)以邻接矩阵或邻接表创建一个图，要求能够动态输入；2)输出深度优先和广度优先遍历序列；3)三选一应用题：1）两种算法构造最小生成树；2）有向无环图的拓扑排序和关键路径计算；3）两种算法计算最短路径。三、设计与编码1)程序结构基本设计框架（提示：请根据所选定题目，描述程序的基本框架，可以用流程图、界面描述图、框图等来表示）2)本实验用到的理论知识图定义、图的两种存储结构的定义、算法，递归的深度优先遍历算法，广度优先遍历算法（提示：总结本实验用到的理论知识，实现理论与实践相结合。总结尽量简明扼要，并与本次实验密切相关，要求结合自己的题目并阐述自己的理解和想法）3)具体算法设计定义邻接矩阵的结构体类型定义图的结构体类型定义邻接表结构体类型、定义相关点和弧的相关信息定义函数（将邻接矩阵转换为邻接表）输出邻接表将邻接表换为邻接矩阵深度优先遍历、广度优先遍历主函数（提示：该部分主要是利用C、C++等完成数据结构定义、设计算法实现各种操作，可以用列表分步形式的自然语言描述，也可以利用流程图等描述）4)编码#includestdio.h#includemalloc.h#definemax100typedefstruct//以下定义临接矩阵类型{intnumber;intinfo;}VertexType;typedefstruct//图的定义{intedges[max][max];intn,e;VertexTypevexs[max];}MGraph;//定义邻接表类型typedefstructANode{intadjvex;structANode*nextarc;//指向下一条弧的指针intinfo;//存放弧的信息（权值）}ArcNode;typedefstructVnode{intdata;ArcNode*firstarc;//指向第一条弧}VNode;typedefVNodeAdjList[max];//AdjList是邻接表类型，把大表变成几个小的连接到一起typedefstruct{AdjListadjlist;intn,e;//图中顶点数和边数}ALGraph;intvisited[max];//全局数组用于判断后面节点是否被访问过voidDispMat(MGraphg)//输出邻接矩阵{inti,j;for(i=0;ig.n;i++){for(j=0;jg.n;j++)if(g.edges[i][j]==0)printf(0);elseprintf(%d,g.edges[i][j]);printf(\n);}}voidMatToList(MGraphg,ALGraph*&G)//将邻接矩阵g转换为邻接表G{inti,j;intn=g.n;ArcNode*p;G=(ALGraph*)malloc(sizeof(ALGraph));for(i=0;in;i++)//给大的邻接表中所有头结点的指针域副初值G-adjlist[i].firstarc=NULL;for(i=0;in;i++)//检查邻接矩阵的每个元素for(j=0;jn;j++)if(g.edges[i][j]!=0){p=(ArcNode*)malloc(sizeof(ArcNode));p-adjvex=j;p-info=g.edges[i][j];p-nextarc=G-adjlist[i].firstarc;//将*p连接到表后G-adjlist[i].firstarc=p;}G-e=g.e;G-n=g.n;}voidDispAdj(ALGraph*G)//输出邻接表{inti;ArcNode*p;for(i=0;iG-n;i++){p=G-adjlist[i].firstarc;if(p!=NULL)printf(%d:,i);while(p!=NULL){printf(%d,p-adjvex);//输出弧的终点p=p-nextarc;}printf(\n);}}voidchange(intvisited[],ALGraph*G)//给全局变量visited赋初值{inti;for(i=0;iG-n;i++)visited[i]=0;}voidListToMat(ALGraph*G,MGraphg)//将邻接表转换为邻接矩阵的形式{inti,j;intn=G-n;ArcNode*p;for(i=0;in;i++)for(j=0;jn;j++)g.edges[i][j]=0;for(i=0;in;i++){p=G-adjlist[i].firstarc;while(p!=NULL){g.edges[i][p-adjvex]=p-info;p=p-nextarc;}}g.n=n;g.e=G-e;}voidDFS(ALGraph*G,intv)//递归深度优先遍历{ArcNode*p;//change(visited,G);visited[v]=1;//第一个点设为已被访问并输出，接着以他为主进行遍历printf(%d,v);p=G-adjlist[v].firstarc;while(p!=NULL){if(visited[p-adjvex]==0)DFS(G,p-adjvex);p=p-nextarc;}}voidBFS(ALGraph*G,intv){ArcNode*p;intqueue[max],front=0,rear=0;//定义循环队列并初始化intvisited[max];intw,i;for(i=0;iG-n;i++)visited[i]=0;printf(%d,v);//把输入的第v个作为第一个广度遍历的节点，一直这样进行下去visited[v]=1;rear=(rear+1)%max;queue[rear]=v;//把v入队while(front!=rear)//队列不为空的时候{front=(front+1)%max;w=queue[front];p=G-adjlist[w].firstarc;while(p!=NULL){if(visited[p-adjvex]==0)//当前节点未被访问{printf(%d,p-adjvex);visited[p-adjvex]=1;rear=(rear+1)%max;queue[rear]=p-adjvex;}p=p-nextarc;}}printf(\n);}voidmain(){inti,j;MGraphg;ALGraph*G;intA[max][4];printf(请输入邻接矩阵：\n);for(i=0;i4;i++)for(j=0;j4;j++)scanf(%d,&A[i][j]);g.n=4;g.e=10;for(i=0;ig.n;i++)for(j=0;jg.n;j++)g.edges[i][j]=A[i][j];//给邻接矩阵赋值printf(这是图的邻接矩阵的形式：);printf(\n);DispMat(g);//输出邻接矩阵的函数G=(ALGraph*)malloc(sizeof(ALGraph));MatToList(g,G);printf(这是图的邻接表的形式：);printf(\n);DispAdj(G);printf(从顶点0开始的深度优先遍历：\n);DFS(G,0);printf(\n);printf(从顶点0开始的广度优先遍历：\n);BFS(G,0);printf(\n);}（提示：该部分主要是将算法转化为C、C++程序，设计主函数完成对各成员函数的调用；设计人机界面，每一步需要用户操作的提示以及每一次用户操作产生的预期结果）四、运行与测试1)在调试程序的过程中遇到什么问题，是如何解决的？2)设计了哪些测试数据？测试结果是什么？3)程序运行结果如何？五、总结与心得学习图的深度和广度优先遍历的内容已有一段时间，这次实验正好能够让我重新回顾一下原来学过的内容，总体感觉，这部分的题做得还可以，可是一上升到程序和算法就有些乱，觉得自己对算法这方面以后还得多看多琢磨。实验完成后的总结与思考，或者谈收获。（注意此部分要结合自己的题目来阐述说明）