数据结构实验五---图的遍历及其应用实现.doc

实验五 图的遍历及其应用实现
一、实验目的
1．熟悉图常用的存储结构。
2．掌握在图的邻接矩阵和邻接表两种结构上实现图的两种遍历方法实现。
3．会用图的遍历解决简单的实际问题。
二、实验内容
[题目] ：从键盘上输入图的顶点和边的信息,建立图的邻接表存储结构,然后以深度优先搜索和广度优先搜索遍历该图,并输出起对应的遍历序列. 试设计程序实现上述图的类型定义和基本操作,完成上述功能。该程序包括图类型以及每一种操作的具体的函数定义和主函数。
三、实验步骤
（一）、数据结构与核心算法的设计描述：
本实验主要在于图的基本操作，关键是图的两种遍历，仔细分析图的遍历的特点，不难发现，其符合递归的特点，因此可以采用递归的方法遍历。本实验图的存储结构主要采用邻接表，总共分为四个模块：图的创建、位置的查找、深度优先遍历、广度优先遍历。
以下是头文件中数据结构的设计和相关函数的声明：
#include<iostream.h>
#include<stdlib.h>
#include<string.h>
#nclude<malloc.h>
#define OVERFLOW -2
#define MAX_VERTEX_NUM 50 //最大顶点数
#define MAXQSIZE 100
# define OK 1
typedef int VRType;
typedef int InfoType;
typedef int QElemType;
typedef enum{DG,DN,UDG,UDN}GraphKind;
typedef struct ArcNode // 弧结点
{
int adjvex; //邻接点域，存放与Vi邻接的点在表头数组中的位置
struct ArcNode *nextarc; //链域指向vi的下一条边或弧的结点，
InfoType *info; //定义与弧相关的权值，无权则为0
}ArcNode;
typedef struct VNode //表头结点
{
char vexdata; //存放顶点信息
struct ArcNode *firstarc; //指示第一个邻接点
}VNode,AdjList[MAX_VERTEX_NUM];
typedef struct
{ //图的结构定义
AdjList vertices; //顶点向量
int vexnum, arcnum; //vexnum为顶点数arcnum为弧或边的个数
GraphKind kind; // 图的种类标志
}MGraph;
typedef struct Queue //构建循环队列
{
QElemType *base;
int front;
int rear;
}Queue;
void CreateGraph(MGraph &G); //图的创建
void DFSTraverse(MGraph &G) ; //深度优先遍历
void BFSTraverse(MGraph &G); //广度优先遍历
int LocateVex(MGraph &G, char &v);//查找顶点v的位置
（二）、函数调用及主函数设计
void main()
{
int x;
MGraph G;
CreateGraph(G);
cout<<"创建图成功!"<<endl;
cout<<"1 深度优先搜索"<<endl<<"2 广度优先搜索"<<endl;
cin>>x;
if(x==1)
{
DFSTraverse(G);
cout<<"深度优先搜索结束!"<<endl;
}
else if(x==2)
{
BFSTraverse(G);
cout<<"广度优先搜索结束!"<<endl;
}
else
cout<<"输入有误!"<<endl<<"再见!"<<endl;
}
（三）、实验总结
由于图的基本操作在图这一章节中起着很主要的作用，所以在实验前就对实验做了充分的准备，实验的成功核心在于两种遍历的实现，因此只有充分理解遍历算法的精髓，才能更好的做好实验。尽管实验过程中不同模块遇到了不同程度的困难，但是经过详细的设计和反复的测试、调试，实验最终结果达到了实验的预期结果。
四、主要算法流程图及程序清单
1、主要算法流程图：
开始
访问V0,置标志
求邻接点w
有？
W访问过？

w→V0

返回
求下一个邻接点

DFS（BFS同DFS类似，故不再列举）
2、程序清单
u 图的创建模块：
void CreateGraph(MGraph &G)
{ // 生成图G的存储结构-邻接表
int i=0,j=0,k; cout<<"\n请输入顶点的数目、边的数目"
cin>>G.vexnum>>G.arcnum>>m; // 输入顶点数、边数和图类
cout<<"\t\t请依次输入各个顶点的数值:";
for(i=0;i<G.vexnum;++i)
{
cin>>G.vertices[i].vexdata;
G.vertices[i].firstarc=NULL;
}
char sv,tv;
cout<<"\t\t请依次输入各边的始点和终点："<<endl;
for (k=0; k<G.arcnum; ++k) // 输入各边并构造邻接表
{
cout<<"请输入第"<<k+1<<"条边的始点：";
cin>>sv;
cout<<"请输入第"<<k+1<<"条边的终点：";
cin>>tv;
i=LocateVex(G, sv);
cout<<"请输入第"<<k+1<<"条边始点的位置为："<<i<<endl;
j=LocateVex(G, tv);
cout<<"请输入第"<<k+1<<"条边终点的位置为："<<j<<endl;
ArcNode *p;
p=(ArcNode *)malloc(sizeof(ArcNode));
if(!p)
{
cout<<"Overflow!";
}
p->adjvex=j;
p->nextarc=G.vertices[i].firstarc;
p->info=NULL;
G.vertices[i].firstarc=p;
if(G.vertices[i].firstarc==NULL)
cout<<"error!";
}
}
u 查找位置模块：
int LocateVex(MGraph &G, char &v)
{
int m;
for(m=0; m<G.arcnum; ++m)
if(G.vertices[m].vexdata==v)
return m;
}
u 深度优先遍历模块：
void DFS(MGraph &G,int v,int *visited); //函数的声明
void DFSTraverse(MGraph &G) // 对图 G 作深度优先遍历
{
int v;
int visited[MAX_VERTEX_NUM];
for (v=0; v<G.vexnum; ++v)
visited[v] =0; // 访问标志数组初始化
for (v=0; v<G.vexnum; ++v)
if (!visited[v])
DFS(G,v,visited); // 对尚未访问的顶点调用DFS
}
void DFS(MGraph &G,int v,int *visited)
{
int w;
char z;
visited[v]=1;
cout<<G.vertices[v].vexdata<<"->";
for(z=G.vertices[v].vexdata;G.vertices[v].firstarc!=NULL; w=G.vertices[v].firstarc->adjvex,
G.vertices[v].firstarc=G.vertices[v].firstarc->nextarc)
if(visited[v]==0)
DFS(G,w,visited);
}
u 广度优先遍历模块：
int InitQueue(Queue &Q) //队列的初始化
{
Q.base=(QElemType *)malloc(MAXQSIZE*sizeof(QElemType));
if(!Q.base)
{ cout<<endl<<"failure! "; return 0; }
Q.front=Q.rear=0;
return (OK);
}
int EnQueue(Queue &Q,QElemType e) //入队
{
if((Q.rear+1)%MAXQSIZE==Q.front)
{ cout<<"队满!"<<endl; return 0; }
Q.base[Q.rear]=e;
Q.rear=(Q.rear+1)%MAXQSIZE;
return (OK);
}
int DeQueue(Queue &Q,QElemType &e) //出队
{
if(Q.front==Q.rear)
{ cout<<"队满!"<<endl; return 0; }
e=Q.base[Q.front];
Q.front=(Q.front+1)%MAXQSIZE;
return (e);
}
int QueueEmpty(Queue &Q) //判断队列是否为空
{
if(Q.front==Q.rear) return (OK);
else return (0);
}
void BFSTraverse(MGraph &G)
{
int v,w,u; int visited[MAX_VERTEX_NUM];
Queue Q;
InitQueue(Q);
for(v=0;v<G.vexnum;++v) visited[v]=0;
for(v=0;v<G.vexnum;++v)
if(visited[v]==0)
{
visited[v]=1;
cout<<G.vertices[v].vexdata<<"->";
EnQueue(Q,v);
while(!QueueEmpty(Q))
{
DeQueue(Q,u);
if(!visited[u])
{
visited[u]=1;
cout<<G.vertices[u].vexdata<<"->";
}
ArcNode* p;
p=G.vertices[u].firstarc;
for(w=u;p!=NULL;w=p->adjvex,p=p->nextarc)
{
if(!visited[w])
EnQueue(Q,w);
}
}
}
}
第 6 页 共 6 页