大家好，欢迎来到IT知识分享网。
数据结构实验报告（六）
一、实验名称
实验六 图的实验1——图的邻接矩阵存储实现
二、 实验目的
1、 熟练理解图的相关概念；
2、 掌握图的邻接矩阵的存储方法的实现；
3、 学会图的遍历算法
三、 实验内容
1、自己确定一个简单无向图（顶点数、和相关结点信息）利用邻接矩阵来实现存储。实现图的构造，并完成：
1） 用深度优先和广度优先两种算法对图进行遍历，输出顶点序列数据；
2） 以合理的格式，输出各个顶点的邻接点；
四、详细设计（C++）
1.算法设计
1. 对于无向图，顶点i的度等于邻接矩阵的第i行（或第i列）非零元素的个数。
2. 要判断顶点i和j之间是否存在边，只需测试邻接矩阵中相应位置的元素arc[i][j]，若其值为1，则有边；否则，顶点i和j之间不存在边。
3. 找顶点i的所有邻接点，依次判别顶点i与其他顶点之间是否有边。
4. 用C++语言中的类实现基于邻接矩阵存储结构下图的抽象数据类型定义。由于图中顶点的数据类型不确定，因此采用C++的模板机制。
构造函数：
构造函数的功能是建立一个含有n个顶点e条边的图，假设建立无向图，算法用伪代码描述如下：
1. 确定图的顶点个数和边的个数；
2. 输入顶点信息存储在一维数组vertex中；
3. 初始化邻接矩阵；
4. 依次输入每条边存储在邻接矩阵arc中：
4.1输入边依附的两个顶点的编号i,j；
4.2将邻接矩阵的第i行第j列的元素值置为1；
4.3将邻接矩阵的第j行第i列的元素值置为1；
2.源程序代码
#include<iostream>
#include<stdlib.h>
using namespace std;
const int MaxSize=10;
int visited[MaxSize]={0};
template<class DataType>
class MGraph
{
public:
MGraph(DataType a[],int n,int e);
~MGraph(){};
void DFSTraverse(int v);
void BFSTraverse(int v);
void Printvertex();
private:
DataType vertex[MaxSize];
int arc[MaxSize][MaxSize];
int vertexNum,arcNum;
};
template<class DataType>
MGraph<DataType>::MGraph(DataType a[],int n,int e)
{
int i,j,k;
vertexNum=n,arcNum=e;
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(int k=0;k<arcNum;k++)
{
cout<<"请输入边之间顶点的编号：";
cin>>i>>j;
arc[i][j]=1;arc[j][i]=1;
}
cout<<endl;
}
template<class DataType>
void MGraph<DataType>::DFSTraverse(int v)
{
cout<<vertex[v];visited[v]=1;
for(int j=0;j<vertexNum;j++)
if(arc[v][j]==1&&visited[j]==0)
DFSTraverse(j);
for(int k=0;k<vertexNum;k++)
if(visited[k]==0)
DFSTraverse(k);
}
template<class DataType>
void MGraph<DataType>::BFSTraverse(int v)
{
int Q[MaxSize];
int front=-1;
int rear=-1;
cout<<vertex[v];visited[v]=1;Q[++rear]=v;
while(front!=rear)
{
v=Q[++front];
for(int j=0;j<vertexNum;j++)
if(arc[v][j]==1&&visited[j]==0)
{
cout<<vertex[j];visited[j]=1;Q[++rear]=j;
}
}
}
template<class DataType>
void MGraph<DataType>::Printvertex()
{
for(int i=0;i<vertexNum;i++)
{
cout<<"顶点"<<vertex[i]<<"的邻接点为：";
for(int j=0;j<vertexNum;j++)
if(arc[i][j]==1)
cout<<vertex[j]<<" ";
cout<<endl;
}
}
int main()
{
char T[8]={'A','B','C','D','E','F','G','H'};
MGraph<char> M(T,8,9);
for(int i=0;i<MaxSize;i++)
{visited[i]=0;}
cout<<"深度优先遍历：";
M.DFSTraverse(0);
cout<<endl;
for(int i=0;i<MaxSize;i++)
{visited[i]=0;}
cout<<"广度优先遍历：";
M.BFSTraverse(0);
cout<<endl;
cout<<endl;
cout<<"各顶点的邻接点如下："<<endl;
M.Printvertex();
cout<<endl;
return 0;
}五、运行与测试结果
六、总结与心得
这次实验主要是参照课本，在理解的基础上完成的。其中在深度遍历的算法中，经过验证，我认为课本的代码是残缺的。其实深度优先遍历有点类似于树中的前序遍历。依据课本的代码，我发现一旦左边的顶点输出完毕后，右边顶点仍没输出就已经退出程序。所以我在输出完左边顶点后又循环判断了右边的顶点是否访问过，若未访问，则将该数值传入进行深度优先遍历。这样一来，所有的顶点都会输出。
免责声明：本站所有文章内容,图片，视频等均是来源于用户投稿和互联网及文摘转载整编而成，不代表本站观点，不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益，请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权，请联系删除，如若转载，请注明出处：https://yundeesoft.com/24268.html
