文档介绍：重庆交通大学设计性实验报告班级:2013级2班学号:姓名:旧城余约实验项目名称:图实验项目性质:设计性实验实验所属课程:算法与数据结构实验室(中心):B01-407指导教师:鲁云平实验完成时间:2015年6月3日教师评阅意见:签名:年月日实验成绩:实验目的熟悉图的存储结构及相关知识;熟悉图的遍历。:图的顶点、存储结构自行定义;:求顶点的度,遍历操作,求最小生成树等。三、实验设备及软件电脑、visualC++;四、实验过程及步骤运行环境:VisualC++;实现思路:对于图的存储方式,我采取了基于数组的邻接矩阵的存储方式。首先,将所有顶点放在顶点表中,然后将边放在邻接矩阵中,有边,则用1(或权值)表示,无边,则用0(或∞)表示,由此,便可以定义图类了。在图类中,数据成员有maxVertices,表示图中最大顶点数,numEdges,表示当前边数,numVertices,表示当前顶点数,以及*VerticesList,表示顶点表,**Edge,表示邻接矩阵;在成员函数中,我定义了输入、输出、计算度数、遍历等函数,以下,我将一一进行说明。1、TGetValue(inti)获取顶点表中i位置的顶点的值,给出i的值,就能根据数组下标的访问方式进行访问。2、EGetWeight(inti,intj)取边(i,j)上的权值,i,j为数组下标,同样的根据数组下标的访问方式进行访问。3、intGetFirstNeighbor(intv)获取顶点表中位置为v的顶点的第一个邻接顶点的的位置,在实现时,直接在邻接矩阵中进行查找,若(v,col)的权值符合要求,则找到,并返回col的值。4、intGetNextNeighbor(intv,intw)获取下一个邻接顶点,实现只需将已找到的顶点位置加一后赋给col,若(v,col)的权值符合要求,则找到,并返回col的值。5、boolRemoveVertex(intv)删除顶点以及各该顶点相关联的边,顶点表中,用最后一个顶点代替位置v的顶点,删除相应的边时,用邻接矩阵最后一列填补到第v列,当然,当前顶点数以及当前边数要减一。6、boolRemoveEdge(intv1,intv2)删除边(v1,v2),要删除边,但不能删除顶点才是满足要求的,这样,只需要将对应边的权值修改为无穷大就行。7、voidDFS(Graphmtx<T,E>&G,T&v),voidDFS(Graphmtx<T,E>&G,intv,boolvisit[])深度优先遍历操作,代码实现分为主过程与子过程,主过程主要定义访问标记指针以及获取开始遍历的第一个顶点位置,然后将其传给子过程,子过程采用递归的方式进行遍历,先查找开始顶点的第一个邻接顶点,若访问标记显示没有被访问过则递归,否则就查找下一个邻接顶点,这三个语句用while循环,递归到开始顶点时结束循环,也即结束递归。8、intGetDegree(Graphmtx<T,E>&G,T&v)计算顶点度数,统计邻接矩阵中第v行中权值符合要求的个数(即0到无穷大)即为顶点v的度数。9、intGetVertexPos(Tvertex)获取顶点vertex在顶点表中的位置,用顺序查找的方式在顶点表(即一位数组)中查找,找到则返回下标。10、boolInsertVertex(T&vertex)插入顶点vertex,即数组的顺序存储。11、boolInsertEdge(intv1,intv2,Ecost)插入边(v1,v2),cost为权值,在邻接矩阵中即用下标存入方式存入权值cost。12、friendistream&operator>>(istream&in,Graphmtx<T,E>&G)重载输入,主要调用插入顶点及插入边这两个函数,先插入顶点,再插入边。13、friendostream&operator<<(ostream&out,Graphmtx<T,E>&G)重载输出,主要用下标方式访问。14、voidPrim(Graphmtx<T,E>&G)构建最小生成树,额外定义了三个数组,*lowcost存放最小权值,*used记录处理过的顶点在顶点表中的位置,*seqnum用来存放顶点的存放顺序,方便后面输出。*lowcost初始化为顶点表中第一个顶点到其他顶点的边上权值,定义一个中间变量min,用循环的方式用lowcost[i]与min作比较,找到符合要求的顶点的位置并记录到used中已处理,同时,将这些顶点位置顺序存放到seqnum中,循环结束时,最小生成树构建完成。(这个函数是最后补上去的)。以上,就是图的定义。在写类时,每写好一个函数便在cpp文件调试,有错时,便走查代码。最后便定义菜单类,本次实验完成。五、主要代码及运行结