数据结构实验七 图及图的操作实验

实验报告七图及图的操作实验班级： 2010XXX 姓名： HoogLe 学号： 2010XXXX 专业： XXXX

*****************

一、实验目的：

1、掌握图的基本概念和术语

2、掌握图的存储结构及创建算法。

3、掌握图的遍历算法（递归算法）。

二、实验内容：

1、图邻接矩阵存储结构表示及基本操作算法实现

[实现提示] （同时可参见教材及ppt上的算法）函数、类名称等可自定义，部分变量请

加上学号后3位。也可自行对类中所定义的操作进行扩展。

所加载的库函数或常量定义及类的定义：

（1）邻接矩阵存储结构类定义：

自定义如下：

#include

using namespace std;

const int MaxSize=12;

const int INFINITY=65535;

template

class Mgraph{

public:

Mgraph(T a[],int n,int e);//构造函数，a[]表示节点数组，n表示顶点个数，e表示边数

void printGraph(); //输出

void BFS(int v,int visited[]); //广度优先搜索

private:

T vertex[MaxSize];

int arc[MaxSize][MaxSize];

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); //有向网

};

template

Mgraph::Mgraph(T a[],int n,int e){

int kind;

cout<<"请输入所需创建的图的类型:"<

cout<<"1.无向图"<

cout<<"2.无向网"<

cout<<"3.有向图"<

cout<<"4.有向网"<

cin>>kind;

switch(kind){

case 1:createUG(a,n,e);break;

case 2:createUW(a,n,e);break;

case 3:createHG(a,n,e);break;

case 4:createHW(a,n,e);break;

default:cout<<"输入错误！"<

}

}

（2）创建邻接矩阵算法

创建无向图邻接矩阵算法：

template

void Mgraph::createUG(T a[],int n,int e)

{//创建无向图

vertexNum=n; //顶点数

arcNum=e; //边数

int i,j,k;

for (i=0; i

vertex[i]=a[i];

for (i=0; i

for (j=0; j

arc[i][j]=0;

for (k=0; k

//依次输入每一条边，并修改邻接矩阵的相应元素{ cout<<"请输入第"<

cin>>i>>j; //边依附的两个顶点的序号

arc[i-1][j-1]=1; //置有边标志

arc[j-1][i-1]=1;

}

}

创建无向网邻接矩阵算法：

无向网的创建：

template

void Mgraph::createUW(T a[],int n,int e)

{//创建无向网

int w;//权值

vertexNum=n; //顶点数

arcNum=e; //边数

int i,j,k;

for (i=0; i

vertex[i]=a[i];

for (i=0; i

for (j=0; j

arc[i][j]=INFINITY;

for (k=0; k

//依次输入每一条边，并修改邻接矩阵的相应元素

{cout<<"请输入第"<

cin>>i>>j>>w;

//边依附的两个顶点的序号

arc[i-1][j-1]=w; //置有边标志

arc[j-1][i-1]=w;

}

}

创建有向图邻接矩阵算法：

template

void Mgraph::createHG(T a[],int n,int e)

{//创建无向图

vertexNum=n; //顶点数

arcNum=e; //边数

int i,j,k;

for (i=0; i

vertex[i]=a[i];

for (i=0; i

for (j=0; j

arc[i][j]=0;

for (k=0; k

//依次输入每一条边，并修改邻接矩阵的相应元素

{ cout<<"请输入第"<

cin>>i>>j; //边依附的两个顶点的序号

arc[i-1][j-1]=1; //置有边标志

}

}

创建有向网邻接矩阵算法：

template

void Mgraph::createHW(T a[],int n,int e)

{//创建无向图

vertexNum=n; //顶点数

arcNum=e; //边数

int i,j,k;

int w;

for (i=0; i

vertex[i]=a[i];

for (i=0; i

for (j=0; j

arc[i][j]=0;

for (k=0; k

{

cout<<"请输入第"<