数据结构图的验证实验
实验九 图验证实验一、邻接矩阵操作验证
1. 实验目的
⑴ 掌握图的逻辑结构；
⑵ 掌握图的邻接矩阵存储结构；
⑶ 掌握图在邻接矩阵存储结构上遍历算法的实现。
2. 实验内容
⑴ 建立无向图的邻接矩阵存储；
⑵ 对建立的无向图，进行深度优先遍历；
⑶ 对建立的无向图，进行广度优先遍历。
3. 实现提示
本题采用图的邻接矩阵存储，即用一维数组存储图中顶点的信息，用二维数组存储图中边的信息（即各顶点之间的邻接关系）。
假设无向图G＝（V，E）有n个顶点，则邻接矩阵是一个n×n的方阵，定义为：
设计实验用邻接矩阵类MGraph，包括遍历操作。
const int MaxSize=10; //图中最多顶点个数
template <class T>
class MGraph
{
public:
MGraph(T a[ ], int n, int e); //构造函数，初始化具有n个顶点e条边的无向图
void DFSTraverse(int v); //深度优先遍历图
void BFSTraverse(int v); //广度优先遍历图
private:
T vertex[MaxSize]; //存放图中顶点的数组
int arc[MaxSize][MaxSize]; //存放图中边的数组
int vertexNum, arcNum; //图的顶点数和边数
};
⑴ 设计构造函数，建立一个无向图的邻接矩阵存储。
假设图的顶点信息存放在数组a[n]中，边的信息（即边所依附的顶点）由键盘输入，建立一个无向图的邻接矩阵存储的算法如下：template <class T>
MGraph::MGraph(T a[ ], int n, int e)
{
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 (k=0; k<arcNum; k++) //依次输入每一条边，并修改邻接矩阵的相应元素
{
cin>>i>>j; //边依附的两个顶点的序号
arc[i][j]=1; //置有边标志
arc[j][i]=1;
}
}
⑵ 深度优先遍历算法
template <class T>
void MGraph::DFSTraverse(int v)
{
cout<<vertex[v]; visited [v]=1;
for (j=0; j<vertexNum; j++)
if (arc[v][j]==1 && visited[j]==0) DFSTraverse( j );
}
⑶ 广度优先遍历算法
template <class T>
void MGraph::BFSTraverse(int v)
{
front=rear=-1; //初始化队列,假设队列采用顺序存储且不会发生溢出
cout<<vertex[v]; visited[v]=1; Q[++rear]=v; //被访问顶点入队
while (front!=rear)
{
v=Q[++front]; //将队头元素出队并送到v中
for (j=0; j<vertexNum; j++)
if (arc[v][j]==1 && visited[j]==0 ) {
cout<<vertex[j]; visited[j]=1; Q[++rear]=j;
}
}
}
二、邻接表操作验证
1. 实验目的
⑴ 掌握图的逻辑结构；
⑵ 掌握图的邻接表存储结构；
⑶ 掌握图的邻接表存储结构下遍历算法的实现。
2. 实验内容
⑴ 建立一个有向图的邻接表存储结构；
⑵ 对建立的有向图，进行深度优先遍历；
⑶ 对建立的有向图，进行广度优先遍历。
3. 实现提示
邻接表存储结构是基于顺序存储与链接存储相结合的存储方法，基本思想是：对于图的每个顶点vi，将所有邻接于vi的顶点链成一个单链表，称为顶点vi的边表（对于有向图则称为出边表），所有顶点的边表的头指针和存储顶点信息的一维数组构成了顶点表。所以，在邻接表中存在两种结点结构，分别是顶点表结点和边表结点，如图9-1所示。
用C++中的结构类型描述上述结点。
struct ArcNode //定义边表结点
{
int adjvex; //邻接点域
ArcNode *next;
};
template <class T>
struct VertexNode //定义顶点表结点
{
T vertex;
ArcNode *firstedge;
};
设计实验用邻接表类ALGraph，包括遍历操作。
const int MaxSize=10; //图的最大顶点数
template <class T>
class ALGraph
{
public:
ALGraph(T a[ ], int n, int e); //构造函数，初始化一个有n个顶点e条边的有向图
~ALGraph( ); //析构函数，释放邻接表中各边表结点的存储空间
void DFSTraverse(int v); //深度优先遍历图
void BFSTraverse(int v); //广度优先遍历图
private:
VertexNode adjlist[MaxSize]; //存放顶点表的数组
int vertexNum, arcNum; //图的顶点数和边数
};
⑴ 设计构造函数，建立有向图的邻接表存储。
template <class T>
ALGraph::ALGraph(T a[ ], int n, int e)
{
vertexNum=n; arcNum=e;
for (i=0; i<vertexNum; i++) //输入顶点信息，初始化顶点表
{
adjlist[i].vertex=a[i];
adjlist[i].firstedge=NULL;
}
for (k=0; k<arcNum; k++) //依次输入每一条边，并在相应边表中插入结点
{
cin>>i>>j; //输入边所依附的两个顶点的序号
s=new ArcNode; s->adjvex=j; //生成一个边表结点s
s->next=adjlist[i].firstedge; //将结点s插入到结点i的边表的表头
adjlist[i].firstedge=s;
}
}
⑵ 深度优先遍历算法如下：
template <class T>
void ALGraph::DFSTraverse(int v)
{
cout<<adjlist[v].vertex; visited[v]=1;
p=adjlist[v].firstedge;
while (p) //依次搜索顶点v的邻接点j
{
j=p->adjvex;
if (visited[j]==0) DFSTraverse(j);
p=p->next;
}
}
⑶ 广度优先遍历算法如下：
template <class T>
void ALGraph::BFSTraverse(int v)
{
front=rear=-1; //初始化队列, 假设队列采用顺序存储且不会发生溢出
cout<<adjlist[v].vertex; visited[v]=1; Q[++rear]=v; //被访问顶点入队
while (front!=rear)
{
v=Q[++front];
p=adjlist[v].firstedge; //边表中的工作指针p初始化
while (p)
{
j= p->adjvex;
if (visited[j]==0) {
cout<<adjlist[j].vertex; visited[j]=1;Q[++rear]=j;
}
p=p->next;
}
}
}
我是新手，请哪位大哥哥大姐姐帮帮忙看看这个怎么写啊。最好多点注释啊。万分感谢啊。。。。
