实验7 图及图的操作实验

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

一、 实验目的：

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

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

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

二、 实验内容：

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

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

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

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

自定义如下：

（2）创建邻接矩阵算法

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

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

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

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

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

#include <iostream>

using namespace std;

const int MaxSize=20;

const int INFINITY=65535;

template<class T>

class Graph{

public:

Graph(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>

Graph<T>::Graph(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;

}

}

template <class T>

void Graph<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 Graph<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 Graph<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 Graph<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; //置有边标志 }

}

template <class T>

void Graph<T>::printGraph()

{//输出邻接矩阵

int i,j;

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

{

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

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

cout<<endl;

}

}

template <class T>

void Graph<T>::BFS(int v,int visited[]){

if (v>vertexNum){ cout<<"元素不存在~！"<<endl; exit(0);} /*构造队列*/

int front=-1;

int rear=-1;

int Queue[MaxSize];

//////////////////

cout<<vertex[v]<<" ";

visited[v]=1;

Queue[++rear]=v;

while (front!=rear)

{

v=Queue[++front]; //将队头元素出队并送到v中

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

if (arc[v][j]==1 && visited[j]==0 ){

cout<<vertex[j]<<" ";

visited[j]=1;

Queue[++rear]=j;//进队

}

}

}

void main(){

char a[5]={'A','B','C','D','E'};

Graph<char> graph1(a,5,8);

graph1.printGraph();

int visited[5]={0};

graph1.BFS(2,visited);

}

测试结果粘贴如下：

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

[实现提示]函数、类名称等可自定义，部分变量请加上学号后3位。也可自行对类中所定义的操作进行扩展。

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

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

自定义如下：

（2）创建邻接表算法

创建无向网邻接表算法：

创建有向网邻接表算法：

（3）输出邻接表结果算法

测试结果粘贴如下：

#include <iostream>

using namespace std;

const int MaxSize=20;

class Edge //边

{

public:

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

Edge *nextarc; //下一条边

int value; //边的权值

};

template<class T> class Graph;

template<class T>

class VertexNode{ //节点

friend class Graph<T>;

T vex; //结点名

Edge *firstarc; //第一个边

};

template<class T>

class Graph{

public:

Graph(T a[],int n,int e);//构造一个有E条边N个结点的图，A[]为结点矩阵

~Graph(); //析构函数

void printGraph(); //输出

void DFS(int v,int visited[]); //深度优先遍历

private:

VertexNode<T> adjlist[MaxSize]; //存放结点

int vertexNum,arcNum; //顶点数和边数

void creatGraphU(T a[],int n,int e); //无向图

void creatGraphH(T a[],int n,int e); //有向图

};

template<class T>

Graph<T>::~Graph(){

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

{

Edge *E,*q;

E=adjlist[i].firstarc;

while(E)

{

q=E;

E=E->nextarc;

delete q;

}

}

}

template<class T>

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

int kind;

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

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

cout<<"-----2.有向图------"<<endl;

cin>>kind;

switch(kind){

case 1:

creatGraphU(a,n,e);break;

case 2:

creatGraphH(a,n,e);break;

default:

cout<<"输入错误！"<<endl;

}

}

template<class T>

void Graph<T>::creatGraphU(T a[],int n,int e){

Edge *E;

vertexNum=n;

arcNum=e;

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

{

adjlist[i].vex=a[i];

adjlist[i].firstarc=NULL;

}

int j,w;

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

{

cout<<"请输入第"<<k+1<<"条弧的信息（格式为：顶点1 顶点2 权值）";

cin>>i>>j>>w;

E=new Edge;

E->value=w;

E->adjvertex=j-1;

E->nextarc=adjlist[i-1].firstarc;

adjlist[i-1].firstarc=E;

E=new Edge;

E->value=w;

E->adjvertex=i-1;

E->nextarc=adjlist[j-1].firstarc;

adjlist[j-1].firstarc=E;

}

}

template<class T>

void Graph<T>::creatGraphH(T a[],int n,int e){

Edge *E;

vertexNum=n;

arcNum=e;

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

{

adjlist[i].vex=a[i];

adjlist[i].firstarc=NULL;

}

int j,w;

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

{

cout<<"请输入第"<<k+1<<"条弧的信息（格式为：起点

";

cin>>i>>j>>w;

E=new Edge;

E->value=w;

E->adjvertex=j-1;

E->nextarc=adjlist[i-1].firstarc;

adjlist[i-1].firstarc=E;

}

}

template<class T>

void Graph<T>::printGraph(){

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

{

Edge *p;

cout<<i<<" ";

p=adjlist[i].firstarc;

while(p)

{ 终点 权值）

cout<<p->adjvertex<<" ";

p=p->nextarc;

}

cout<<endl;

}

}

template<class T>

void Graph<T>::DFS(int v,int visited[]){

if(v>vertexNum){ cout<<"顶点数处错误"<<endl; exit(0);}

Edge *p;

int j;

cout<<adjlist[v].vex<<" ";

visited[v]=1;

p=adjlist[v].firstarc;

while (p!=NULL) //依次搜索顶点v的邻接点j {

j=p->adjvertex;

if (visited[j]==0) DFS(j,visited);

p=p->nextarc;

}

}

void main()

{

char a[5]={'A','B','C','D','E'};

Graph<char> graph1(a,5,8);

graph1.printGraph();

int visited[5]={0};

graph1.DFS(2,visited);

}

3、图的遍历递归算法

（1）（存储结构为邻接表）深度优先遍历算法

递归算法：

测试结果粘贴如下：

有向网的测试结果：

无向网的测试结果：

（2）广度优先遍历算法

非递归算法

测试结果粘贴如下：

有向网的测试结果：

无向网的测试结果：

三、 实验心得（含上机中所遇问题的解决办法，所使用到的编程技巧、创新

点及编程的心得）

本文来源：https://www.bwwdw.com/article/ptqm.html