实验7图及图的操作实验.doc

实验报告七 图及图的操作实验班级： 姓名： 学号： 专业： 一、 实验目的：1、掌握图的基本概念和术语2、掌握图的存储结构及创建算法。3、掌握图的遍历算法（递归算法）。二、 实验内容：1、图邻接矩阵存储结构表示及基本操作算法实现实现提示 （同时可参见教材及ppt上的算法）函数、类名称等可自定义，部分变量请加上学号后3位。也可自行对类中所定义的操作进行扩展。所加载的库函数或常量定义及类的定义：（1）邻接矩阵存储结构类定义：自定义如下：const int MaxSize=4;const int INFINITY=65535;template class Mgraphpublic: Mgraph(T a,int n,int e); void PGraph();private: T vertexMaxSize; int arcMaxSizeMaxSize; int vertexNum,arcNum; void createUG(T a,int n,int e); void createUW(T a,int n,int e); void createHG(T a,int n,int e); void createHW(T a,int n,int e); ;（2）创建邻接矩阵算法创建无向图邻接矩阵算法：template void Mgraph:createUG(T a,int n,int e) vertexNum=n; arcNum=e; int i,j,k; for (i=0; ivertexNum; i+) vertexi=ai; for (i=0; ivertexNum; i+) for (j=0; jvertexNum; j+) arcij=0; for (k=0; karcNum; k+) cout请输入第k+1ij; arcij=1; arcji=1; 创建无向网邻接矩阵算法：template void Mgraph:createUW(T a,int n,int e) int w; vertexNum=n; arcNum=e; int i,j,k; for (i=0; ivertexNum; i+) vertexi=ai; for (i=0; ivertexNum; i+) for (j=0; jvertexNum; j+) arcij=INFINITY; for (k=0; karcNum; k+) cout请输入第k+1ijw; arcij=w; arcji=w; 创建有向图邻接矩阵算法：template void Mgraph:createHG(T a,int n,int e) vertexNum=n; arcNum=e; int i,j,k; for (i=0; ivertexNum; i+) vertexi=ai; for (i=0; ivertexNum; i+) for (j=0; jvertexNum; j+) arcij=0; for (k=0; karcNum; k+) cout请输入第k+1ij; arcij=1; 创建有向网邻接矩阵算法：template void Mgraph:createHW(T a,int n,int e) int w; vertexNum=n; arcNum=e; int i,j,k; for (i=0; ivertexNum; i+) vertexi=ai; for (i=0; ivertexNum; i+) for (j=0; jvertexNum; j+) arcij=INFINITY; for (k=0; karcNum; k+) cout请输入第k+1ijw; arcij=w;（3）输出邻接矩阵结果算法template void Mgraph:PGraph()int i,j;for(i=0;ivertexNum;i+)for(j=0;jvertexNum;j+)coutarcijendl;coutendl;测试结果粘贴如下：无向图无向网有向图有向网2、图邻接表存储结构表示及基本操作算法实现实现提示函数、类名称等可自定义，部分变量请加上学号后3位。也可自行对类中所定义的操作进行扩展。所加载的库函数或常量定义及类的定义：（1）邻接表存储结构类定义：自定义如下：#includeusing namespace std;const int MaxSize=4;class ArcNodepublic: int adjvex; ArcNode *nextarc; int info;template class BGraph;template class VertexNode friend class BGraph; T vex; ArcNode *firstarc;template class BGraphpublic: BGraph(T a , int n, int e); BGraph(); void pGraph();private: VertexNode adjlistMaxSize; int vertexNum, arcNum;（2）创建邻接表算法创建无向网邻接表算法：template BGraph:BGraph(T a , int n, int e)int i,j,k,w;ArcNode *E;vertexNum=n;arcNum=e; for(i=0;ivertexNum;i+)adjlisti.vex=ai; adjlisti.firstarc=NULL;for(k=0;karcNum;k+) cout请输入第k+1ijw;E=new ArcNode;E-info=w;E-adjvex=j;E-nextarc=adjlisti.firstarc;adjlisti.firstarc=E;E=new ArcNode;E-info=w;E-adjvex=i;E-nextarc=adjlistj.firstarc;adjlistj.firstarc=E;创建有向网邻接表算法：template BGraph:BGraph(T a , int n, int e)int i,j,k,w;ArcNode *E;vertexNum=n;arcNum=e; for(i=0;ivertexNum;i+)adjlisti.vex=ai; adjlisti.firstarc=NULL;for(k=0;karcNum;k+) cout请输入第k+1ijw;E=new ArcNode;E-info=w;E-adjvex=j;E-nextarc=adjlisti.firstarc;adjlisti.firstarc=E;（3）输出邻接表结果算法template void BGraph:pGraph()for(int i=0;ivertexNum;i+)ArcNode *E;E=adjlisti.firstarc;while(E) coutadjvexnextarc; 测试结果粘贴如下：无