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

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

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

2858505197@

一、 实验目的：

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

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

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

二、 实验内容：

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

[实现提示] （同时可参见教材及ppt上的算法）函数、类名称等可自定义，部分变量请加上学号后3位。也可自行对类中所定义的操作进行扩展。

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

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

自定义如下：

#include <iostream>

using namespace std;

const int MaxSize=12;

const int INFINITY=65535;

template<class T>

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<class T>

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

int kind;

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

cout<<"1.无向图"<<endl;

cout<<"2.无向网"<<endl;

cout<<"3.有向图"<<endl;

cout<<"4.有向网"<<endl;

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<<"输入错误！"<<endl;

}

}

（2）创建邻接矩阵算法

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

template <class T>

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

{//创建无向图

vertexNum=n; //顶点数

arcNum=e; //边数

int i,j,k;

for (i=0; i<vertexNum; i++)

vertex[i]=a[i];

for (i=0; i<vertexNum; i++) //初始化邻接矩阵

for (j=0; j<vertexNum; j++)

arc[i][j]=0;

for (k=0; k<arcNum; k++)

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

{ cout<<"请输入第"<<k+1<<"条边(格式：顶点1 顶点2):"; cin>>i>>j; //边依附的两个顶点的序号

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

arc[j-1][i-1]=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++)

vertex[i]=a[i];

for (i=0; i<vertexNum; i++) //初始化邻接矩阵

for (j=0; j<vertexNum; j++)

arc[i][j]=INFINITY;

for (k=0; k<arcNum; k++)

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

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

{cout<<"请输入第"<<k+1<<"条边(格式：顶点1 顶点2 权值):"; cin>>i>>j>>w;

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

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

arc[j-1][i-1]=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++)

vertex[i]=a[i];

for (i=0; i<vertexNum; i++) //初始化邻接矩阵

for (j=0; j<vertexNum; j++)

arc[i][j]=0;

for (k=0; k<arcNum; k++)

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

{ cout<<"请输入第"<<k+1<<"条边(格式：顶点1 顶点2):"; cin>>i>>j; //边依附的两个顶点的序号

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

}

}

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

template <class T>

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

{//创建无向图

vertexNum=n; //顶点数

arcNum=e; //边数

int i,j,k;

int w;

for (i=0; i<vertexNum; i++)

vertex[i]=a[i];

for (i=0; i<vertexNum; i++) //初始化邻接矩阵

for (j=0; j<vertexNum; j++)

arc[i][j]=0;

for (k=0; k<arcNum; k++)//依次输入每一条边，并修改邻接矩阵的相应元素

{

cout<<"请输入第"<<k+1<<"条边(格式：顶点1 顶点2 权值):";

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

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

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

}

（3）输出邻接矩阵结果算法

template <class T>

void Mgraph<T>::printGraph()

{//输出邻接矩阵

int i,j;

for(i=0;i<vertexNum;i++)

{

for(j=0;j<vertexNum;j++)

cout<<arc[i][j]<<ends;

cout<<endl;

}

}

测试结果粘贴如下：

void main()

{

int a[6]={1,2,3,4,5,6};

Graph<int> graph1(a,6,5);

graph1.printGraph();

}

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

[实现提示]函数、类名称等可自定义，部分变量请加上学号后3位。也可自行

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

对类中所定义的操作进行扩展。

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

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

自定义如下：

#include <iostream>

using namespace std;

const int MaxSize=12;

class Edge //边

{

public:

int adjvertex; //当前结点的下标

Edge *nextarc; //下一条边

int value; //边的权值

};

template<class T> …… 此处隐藏：2767字，全部文档内容请下载后查看。喜欢就下载吧 ……