图实验报告

重庆交通大学设计性实验报告班级:2013级2班学号：姓名：旧城余约实验项目名称：图实验项目性质：设计性实验实验所属课程：算法与数据结构实验室(中心)：B01-407指导教师：鲁云平实验完成时间：2015年6月3日一、实验目的1、熟悉图的存储结构及相关知识；2、熟悉图的遍历。二、实验内容及要求1.完成一个带树图的存储：图的顶点、存储结构自行定义;2.主要完成以下功能：求顶点的度，遍历操作，求最小生成树等。三、实验设备及软件电脑、visualC++6.0；四、实验过程及步骤运行环境：VisualC++6.0；实现思路：对于图的存储方式，我采取了基于数组的邻接矩阵的存储方式。首先，将所有顶点放在顶点表中，然后将边放在邻接矩阵中，有边，则用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(GraphmtxT,E&G,T&v)，voidDFS(GraphmtxT,E&G,intv,boolvisit[])深度优先遍历操作，代码实现分为主过程与子过程，主过程主要定义访问标记指针以及获取开始遍历的第一个顶点位置，然后将其传给子过程，子过程采用递归的方式进行遍历，先查找开始顶点的第一个邻接顶点，若访问标记显示没有被访问过则递归，否则就查找下一个邻接顶点，这三个语句用while循环，递归到开始顶点时结束循环，也即结束递归。8、intGetDegree(GraphmtxT,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,GraphmtxT,E&G)重载输入，主要调用插入顶点及插入边这两个函数，先插入顶点，再插入边。13、friendostream&operator(ostream&out,GraphmtxT,E&G)重载输出，主要用下标方式访问。14、voidPrim(GraphmtxT,E&G)构建最小生成树，额外定义了三个数组，*lowcost存放最小权值，*used记录处理过的顶点在顶点表中的位置，*seqnum用来存放顶点的存放顺序，方便后面输出。*lowcost初始化为顶点表中第一个顶点到其他顶点的边上权值，定义一个中间变量min，用循环的方式用lowcost[i]与min作比较，找到符合要求的顶点的位置并记录到used中已处理，同时，将这些顶点位置顺序存放到seqnum中，循环结束时，最小生成树构建完成。（这个函数是最后补上去的）。以上，就是图的定义。在写类时，每写好一个函数便在cpp文件调试，有错时，便走查代码。最后便定义菜单类，本次实验完成。五、主要代码及运行结果主要代码：1、main函数#includeiostream.h#includeMENU.Hintmain(){Graphmtxdouble,doubleob1;Menudouble,doubleob2;ob2.Menu1(ob1);return0;}2、图类#includeiostream.h#includelimits.hconstintDefaultVertices=30;templateclassT,classEclassGraph//图的类定义{public:Graph(intsz=DefaultVertices)//构造函数{maxVertices=sz;numVertices=0;numEdges=0;}~Graph(){}//析构函数boolGraphEmpty()//判断图是够为空{if(numEdges==0)returntrue;elsereturnfalse;}boolGraphFull()//判断是否满了{if(numVertices==maxVertices||numEdges==maxVertices*(maxVertices-1)/2)returntrue;elsereturnfalse;}intNumberOfVertices()//返回当前顶点数{returnnumVertices;}intNumberOfEdges()//返回当前边数{returnnumEdges;}protected:intmaxVertices;//最大顶点数intnumEdges;//当前边数intnumVertices;//当前顶点数};templateclassT,classEclassGraphmtx:publicGraphT,E{friendistream&operator(istream&in,GraphmtxT,E&G);//重载输入friendostream&operator(ostream&out,GraphmtxT,E&G);//重载输出public:Graphmtx(intsz=DefaultVertices);//构造函数~Graphmtx()//析构函数{delete[]VerticesList;delete[]Edge;}TGetValue(inti)//取顶点i的值{returni=0&&i=numVertices?VerticesList[i]:NULL;}EGetWeight(inti,intj)//取边（i，j）上的权值,i,j为数组下标{returni!=-1&&j!=-1?Edge[i][j]:0;}intGetFirstNeighbor(intv);//取顶点v的第一个临接顶点intGetNextNeighbor(intv,intw);//取v的临接顶点w的下一个临接顶点boolInsertVertex(T&vertex);//插入顶点vertexboolInsertEdge(intv1,intv2,Ecost);//插入边（v1,v2），权值为costboolRemoveVertex(intv);//删除顶点v和所有与他相关联的边boolRemoveEdge(intv1,intv2);//在图中删除边（v1,v2）voidDFS(GraphmtxT,E&G,T&v);//深度优先递归算法主过程voidDFS(GraphmtxT,E&G,intv,boolvisit[]);//深度优先递归算法子过程intGetDegree(GraphmtxT,E&G,T&v);//计算顶点度数intGetVertexPos(Tvertex)//给出顶点vertex在图中的位置{for(inti=0;inumVertices;i++)if(VerticesList[i]==vertex)returni;return-1;}voidPrim(GraphmtxT,E&G);private:T*VerticesList;//顶点表E**Edge;//邻接矩阵};templateclassT,classEGraphmtxT,E::Graphmtx(intsz)//构造函数{maxVertices=sz;numVertices=0;numEdges=0;inti,j;VerticesList=newT[maxVertices];//创建顶点表数组Edge=(E**)newE*[maxVertices];//创建邻接矩阵数组for(i=0;imaxVertices;i++)Edge[i]=newE[maxVertices];for(i=0;imaxVertices;i++)//邻接矩阵初始化for(j=0;jmaxVertices;j++)Edge[i][j]=(i==j)?0:INT_MAX;//INT_MAX表示无穷大}templateclassT,classEintGraphmtxT,E::GetFirstNeighbor(intv)//查找顶点位置为v的第一个邻接顶点的位置，若找不到，返回-1{if(v!=-1){for(intcol=0;colnumVertices;col++)if(Edge[v][col]0&&Edge[v][col]INT_MAX)returncol;}return-1;}templateclassT,classEintGraphmtxT,E::GetNextNeighbor(intv,intw)//给出顶点v的某邻接顶点w的下一邻接顶点{if(v!=-1&&w!=-1){for(intcol=w+1;colnumVertices;col++)if(Edge[v][col]0&&Edge[v][col]INT_MAX)returncol;}return-1;}templateclassT,classEboolGraphmtxT,E::InsertVertex(T&vertex)//插入顶点vertex{if(numVertices==maxVertices)returnfalse;//顶点表满，不插入VerticesList[numVertices++]=vertex;returntrue;}templateclassT,classEboolGraphmtxT,E::InsertEdge(intv1,intv2,Ecost)//插入边（v1,v2），权值为cost{if(v1-1&&v1numVertices&&v2-1&&v2numVertices&&Edge[v1][v2]==INT_MAX)//插入条件{Edge[v1][v2]=Edge[v2][v1]=cost;numEdges++;returntrue;}elsereturnfalse;}templateclassT,classEboolGraphmtxT,E::RemoveVertex(intv)//删除顶点v和所有与它相关联的边{if(v0||v=numVertices)//v不在图中，不删{cout该顶点