实验7 图及图的操作实验

1、实验报告七 图及图的操作实验班级： 姓名： 学号： 专业： 一、 实验目的：1、掌握图的基本概念和术语2、掌握图的存储结构及创建算法。3、掌握图的遍历算法（递归算法）。二、 实验内容：1、图邻接矩阵存储结构表示及基本操作算法实现实现提示 （同时可参见教材及ppt上的算法）函数、类名称等可自定义，部分变量请加上学号后3位。也可自行对类中所定义的操作进行扩展。所加载的库函数或常量定义及类的定义：（1）邻接矩阵存储结构类定义：自定义如下：const int MaxSize=4;const int INFINITY=65535;template <class T>class Mgraphp

2、ublic: 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 <class T>void Mg

3、raph<T>:createUG(T a,int n,int e) vertexNum=n; arcNum=e; int i,j,k; for (i=0; i<vertexNum; i+) vertexi=ai; for (i=0; i<vertexNum; i+) for (j=0; j<vertexNum; j+) arcij=0; for (k=0; k<arcNum; k+) cout<<"请输入第"<<k+1<<"条边(格式：顶点1 顶点2):" cin>>i&

4、gt;>j; arcij=1; arcji=1; 创建无向网邻接矩阵算法：template <class T>void Mgraph<T>:createUW(T a,int n,int e) int w; vertexNum=n; arcNum=e; int i,j,k; for (i=0; i<vertexNum; i+) vertexi=ai; for (i=0; i<vertexNum; i+) for (j=0; j<vertexNum; j+) arcij=INFINITY; for (k=0; k<arcNum; k+) cou

5、t<<"请输入第"<<k+1<<"条边(格式：顶点1 顶点2 权值):" cin>>i>>j>>w; arcij=w; arcji=w; 创建有向图邻接矩阵算法：template <class T>void Mgraph<T>:createHG(T a,int n,int e) vertexNum=n; arcNum=e; int i,j,k; for (i=0; i<vertexNum; i+) vertexi=ai; for (i=0; i<v

6、ertexNum; i+) for (j=0; j<vertexNum; j+) arcij=0; for (k=0; k<arcNum; k+) cout<<"请输入第"<<k+1<<"条边(格式：顶点1 顶点2):" cin>>i>>j; arcij=1; 创建有向网邻接矩阵算法：template <class T>void Mgraph<T>:createHW(T a,int n,int e) int w; vertexNum=n; arcNum=e;

7、int i,j,k; for (i=0; i<vertexNum; i+) vertexi=ai; for (i=0; i<vertexNum; i+) for (j=0; j<vertexNum; j+) arcij=INFINITY; for (k=0; k<arcNum; k+) cout<<"请输入第"<<k+1<<"条边(格式：顶点1 顶点2 权值):" cin>>i>>j>>w; arcij=w;（3）输出邻接矩阵结果算法template <

8、class T>void Mgraph<T>:PGraph()int i,j;for(i=0;i<vertexNum;i+)for(j=0;j<vertexNum;j+)cout<<arcij<<endl;cout<<endl;测试结果粘贴如下：无向图无向网有向图有向网2、图邻接表存储结构表示及基本操作算法实现实现提示函数、类名称等可自定义，部分变量请加上学号后3位。也可自行对类中所定义的操作进行扩展。所加载的库函数或常量定义及类的定义：（1）邻接表存储结构类定义：自定义如下：#include<iostream>us

9、ing namespace std;const int MaxSize=4;class ArcNodepublic: int adjvex; ArcNode *nextarc; int info;template <class T> class BGraph;template <class T>class VertexNode friend class BGraph<T> T vex; ArcNode *firstarc;template <class T>class BGraphpublic: BGraph(T a , int n, int e

10、); BGraph(); void pGraph();private: VertexNode<T> adjlistMaxSize; int vertexNum, arcNum;（2）创建邻接表算法创建无向网邻接表算法：template <class T>BGraph<T>:BGraph(T a , int n, int e)int i,j,k,w;ArcNode *E;vertexNum=n;arcNum=e; for(i=0;i<vertexNum;i+)adjlisti.vex=ai; adjlisti.firstarc=NULL;for(k=0;

11、k<arcNum;k+) cout<<"请输入第"<<k+1<<"条弧的信息（格式为：顶点1 顶点2 权值）" cin>>i>>j>>w;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;adjl

12、istj.firstarc=E;创建有向网邻接表算法：template <class T>BGraph<T>:BGraph(T a , int n, int e)int i,j,k,w;ArcNode *E;vertexNum=n;arcNum=e; for(i=0;i<vertexNum;i+)adjlisti.vex=ai; adjlisti.firstarc=NULL;for(k=0;k<arcNum;k+) cout<<"请输入第"<<k+1<<"条弧的信息（格式为：顶点1 顶点2 权值）" cin>>i>>j>>w;E=new ArcNode;E->info=w;E->adjvex=j;E->nextarc=adjlisti.firstarc;adjlisti.firstarc=E;（3）输出邻接表结果算法template <class T>void BGraph<T>:pGraph()for(int i=0;i<vertexNum;i+)ArcNode *E;E=adjlisti.firstarc;while(E) cout<<E-