数据结构实验三

实验报告学院（系）名称：计算机科学与工程学院姓名赵振宇学号20175302专业计算机科学与技术班级2017级4班实验项目实验三：图的遍历与应用课程名称数据结构与算法课程代码0661913实验时间2019年5月27日第3、4节实验地点7-219考核标准实验过程25分程序运行20分回答问题15分实验报告30分特色功能5分考勤违纪情况5分成绩成绩栏其它批改意见:教师签字：考核内容评价在实验课堂中的表现，包括实验态度、编写程序过程等内容等。□功能完善,□功能不全□有小错□无法运行○正确○基本正确○有提示○无法回答○完整○较完整○一般○内容极少○无报告○有○无○有○无一、实验目的1、实验目的：通过实验使学生理解图的主要存储结构，掌握图的构造算法、图的深度优先和广度优先遍历算法，能运用图解决具体应用问题。二、实验题目与要求要求：第1题为必做题，2，3，4至少选一1.输入指定的边数和顶点数建立图，并输出深度优先遍历和广度优先遍历的结果。1）问题描述：在主程序中设计一个简单的菜单，分别调用相应的函数功能：1…图的建立2…深度优先遍历图3…广度优先遍历图0…结束2）实验要求：在程序中定义下述函数，并实现要求的函数功能：CreateGraph():按从键盘的数据建立图DFSGrahp()：深度优先遍历图BFSGrahp()：广度优先遍历图3）实验提示:图的存储可采用邻接表或邻接矩阵；图存储数据类型定义（邻接表存储）#defineMAX_VERTEX_NUM8//顶点最大个数typedefstructArcNode{intadjvex;structArcNode*nextarc;intweight;//边的权}ArcNode;//表结点#defineVertexTypeint//顶点元素类型typedefstructVNode{intdegree,indegree;//顶点的度，入度VertexTypedata;ArcNode*firstarc;}Vnode/*头结点*/,AdjList[MAX_VERTEX_NUM];typedefstruct{AdjListvertices;intvexnum,arcnum;//顶点的实际数，边的实际数}ALGraph;4）注意问题:注意理解各算法实现时所采用的存储结构。注意区别正、逆邻接。2.教学计划编制问题1）问题描述：软件专业的学生要学习一系列课程，其中有些课程必须在其先修课完成后才能学习。2）实验要求：假设每门课程的学习时间为一个学期，试为该专业的学生设计教学计划，使他们能在最短时间内修完专业要求的全部课程。3)实现提示：以顶点代表课程，弧代表课程的先后修关系，按课程先后关系建立有向无环图。利用拓扑排序实现。3.给定实际背景，解决最短路径问题1）问题描述：假设以一个带权有向图表示某一区域的公交线路网，图中顶点代表一些区域中的重要场所，弧代表已有的公交线路，弧上的权表示该线路上的票价（或搭乘所需时间），试设计一个交通指南系统，指导前来咨询者以最低的票价或最少的时间从区域中的某一场所到达另一场所。2）实验要求：利用Dijkstra算法求最低的票价3)实现提示：该问题可以归结为一个求带权有向图中顶点间最短路径的问题。建立以票价为权的有向图，再利用Dijkstra算法求最短路径及其路径长度。4．利用最小生成树算法解决通信网的总造价最低问题1）问题描述：若在n个城市之间建通信网络，架设n-1条线路即可。如何以最低的经济代价建设这个通信网，是一个网络的最小生成树问题。2）实验要求：利用Prim算法求网的最小生成树。3)实现提示：通信线路一旦建立，必然是双向的。因此，构造最小生成树的网一定是无向网。为简单起见，图的顶点数不超过10个，网中边的权值设置成小于100。三、实验过程与实验结果1.输入指定的边数和顶点数建立图，并输出深度优先遍历和广度优先遍历的结果。数据结构为：typedefstructGraph{intvertex[MAX_VERTEX_NUM];//顶点信息intadj[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//邻接矩阵}Graph;本题采用的是邻接矩阵来存储图，用一个一维数组vertex来存放顶点本身，用一个二维数组adj来表示各个顶点之间的邻接关系。图的深度优先遍历，从图中任一顶点v开始访问，然后访问它的任一邻接顶点w1；再从w1出发，访问与其邻接但还没访问过的顶点w2；然后再从w2出发，进行类似的访问，···,如此进行下去，直至到达所有的邻接顶点都被访问过的顶点u为止；接着退回一部，回溯到u的前一个邻接点，看它是否还有其它没有被访问的邻接点。如果有，则访问此节点；若没有，就再退回一步进行搜索。重复上述过程，直至图中所有和v连通的顶点都被访问到。图的广度优先遍历，要借助队列实现。广度优先搜索类似于树的层次遍历过程。它需要借助一个队列来实现。要想遍历每一个顶点，我们可以设v为第一层，再逐个遍历每一层的每个顶点。首先创建一个visited数组，用来记录已被访问过的顶点，然后创建一个队列，用来存放每一层的顶点。从图中的v开始访问，将已访问过的visited[v]数组的值设置为true，同时将v入队。只要队列不空，则重复如下操作：(1)队头顶点u出队。(2)依次检查u的所有邻接顶点w，若visited[w]的值为false，则访问w，并将visited[w]置为true，同时将w入队。测试结果：2.教学计划编制问题。数据结构为：typedefstructGraph{intvertex[MAX_VERTEX_NUM];//顶点intAdj[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//邻接矩阵}Graph;本题依旧采用的是邻接矩阵来存储图，用一个一维数组vertex来存放顶点本身，用一个二维数组adj来表示各个顶点之间的邻接关系。拓扑排序。首先增设一个一维数组indegree来存放每一个顶点的入度。入度为零表示没有前驱节点，删除该顶点以及它的出弧就等价于弧头顶点的入度减1。要实现拓扑算法可以借助堆栈，凡是网中入度为零的顶点都将其进栈。具体步骤为：1）将没有前驱结点（入度为零）的顶点进栈；2）从栈中退出栈顶元素输出，并把该顶点引出的所有弧删去，即把它的各个邻接点的入度减1，同时将当前已输出的顶点个数加1；3）将新的入度为零的顶点再进栈；4）重复2）、3）两步，直到栈空为止。此时或者已输出全部顶点，或者剩下的顶点没有入度为零的顶点。栈在这里的作用只是保存当前入度为零的顶点，并使之处理有序。测试结果：3.给定实际背景，解决最短路径问题。数据结构为：typedefstructGraph{intvertex[MAX_VERTEX_NUM];//顶点intAdj[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//邻接矩阵}Graph;本题还是采用的是邻接矩阵来存储图，用一个一维数组vertex来存放顶点本身，用一个二维数组adj来表示各个顶点之间的邻接关系，二维数组的值表示权值。Dijkstra算法。为了球最短路径采用三个数组：1）S数组，S[i]=0表示顶点i未进入S集合，S[i]=1表示顶点i已进入S集合；2）dist[i]表示当前已知的从源点到顶点i的最短路径长度；3）path[i]表示在当前已知的从源点到顶点i的最短路径上，i前面的那个顶点的下标。把图中顶点集合V分成两组，第一组为已求出最短路径的顶点集合（用S表示，初始时S中只有一个源点，以后每求得一条最短路径,就将加入到集合S中，直到全部顶点都加入到S中，算法就结束了），第二组为其余未确定最短路径的顶点集合（用U表示），按最短路径长度的递增次序依次把第二组的顶点加入S中。在加入的过程中，总保持从源点v到S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度。此外，每个顶点对应一个距离，S中的顶点的距离就是从v到此顶点的最短路径长度，U中的顶点的距离，是从v到此顶点只包括S中的顶点为中间顶点的当前最短路径长度。测试结果：4．利用最小生成树算法解决通信网的总造价最低问题。数据结构为：typedefstructGraph{intvertex[MAX_VERTEX_NUM];//顶点intAdj[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//邻接矩阵}Graph;本题仍然采用的是邻接矩阵来存储图，用一个一维数组vertex来存放顶点本身，用一个二维数组adj来表示各个顶点之间的邻接关系，二维数组的值表示权值。Prim算法。在图中任取一个顶点k作为起始点，令U={k}，以后每一步从一个顶点在U中，而另一个顶点不在U中的各条边中选择权值最小的边，把它作为最小生成树的边保存起来，并将它的顶点加入集合U中。如此继续下去，直到网络中的所有顶点都加入到生成树顶点集合U中为止。为实现Prim算法，需设置一个辅助数组closedge，以记录从U到V-U具有最小权值的边。对每个顶点v属于V-U，在辅助数组中存在一个相应分量closedge[v]，它包括两个域，其中lowcost域用来保存集合U中各顶点与该顶点构成的边中具有最小权值的边的权值。即closedge[v].lowcost=min{wuv|u∈U}。假设初始状态时U={k}(k为出发的顶点)，这时有closedge[k].lowcost=0,表示顶点k已加人集合U中。然后不断选取权值最小的边(v,u)(u∈U,v∈V-U),每选取一条边，就将closedge[v].lowcost置为0,表示顶点v加入集合U。由于顶点v从集合V-U进人集合U后，这两个集合的内容发生了变化，就需要依据新的情况更新每一个不属于U集的顶点的lowcost值。然后再选取出lowcost值最小的顶点加人集合U,依次类推，直至所有顶点都加入集合U为止。测试结果：四、收获与体会通过本次实验，加深了对图的基本了解，同时也练习了对图的一些操作，如：以邻接矩阵方式来存储建立图；深度优先搜索遍历图和广度优先搜索遍历图；拓扑排序；Dijkstra算法以及Prim算法等。对图的理解诶以及基本运用有了些许了解。五、源代码清单1.输入指定的边数和顶点数建立图，并输出深度优先遍历和广度优先遍历的结果。#includestdio.h#includestdlib.h#includestring.h#defineMAX_VERTEX_NUM20typedefstructGraph{intvertex[MAX_VERTEX_NUM];intadj[MAX_VERTEX_NUM][MAX_VERTEX_NUM];}Graph;typedefstructQNode//结点结构{intdata;structQNode*next;}QNode,*QueuePtr;/*队列的数据结构*/typedefstruct{intelem[MAX_VERTEX_NUM];intfront,rear;}Queue;GraphG;intvisited[MAX_VERTEX_NUM];GraphCreateAG(intn,intm){inti=0,j=0,a=0,b=0;for(i=0;in;i++){G.vertex[i]=i+1;}for(i=0;in;i++)for(j=0;jn;j++){G.adj[i][j]=0;}for(i=0;im;i++){scanf(%d%d,&a,&b);G.adj[a-1][b-1]=G.adj[b-1][a-1]=1;}returnG;}/*深度优先遍历*/intcount=0;voidDFS(inti,intn){count++;visited[i]=1;printf(%d,G.vertex[i]);if(countn)printf();for(intj=0;jn;j++)if(G.adj[i][j]&&(!visited[j]))DFS(j,n);}/*入队列*/voidEnQueue(Queue*q,inte){if