数据结构实验五（图的遍历）

数据结构实验五实验报告

实验名称：图的遍历

姓名：黄州龙 班级：08软件工程A班 学号：0825121022

一、 需求分析

1、 本实验要求要利用图论的一些基本概念和算法来

实现对无向图和有向图的2种遍历，分别是深度优先遍历(DFS)和广度优先遍历(BFS)，通过本实验对图遍历算法的实现来帮助了解图这一特殊(多对多)的数据结构，以便在以后的实际应用中可以以此为基础来进行更好的软件程序开发；

2、 该程序开始时是通过用户输入的图的数据文件

(.txt)所在的路径来读取对应文件中的图的数据，以此来构建，进而调用遍历算法函数来对图进行遍历，如果文件不存在或路径不正确，程序将会报告错误并终止；

3、 本程序读取的文件的格式是.txt文件，其中存储的

数据组成如下:

第一行:M N， M是图中结点的个数，N是图中

弧的条数

第二行:D ，D是1或0, 1表示该图是一个有向图，

0表示该图是一个无向图

第三行:M个互不相同的字符，代表每个结点的字

符数据

接下来的N行，每行有2个字母P1、P2，对于有

向图，表示存在一条从P1到P2的有向边；

对于无向图，表示在P1和P2之间存在一条边；

4、 程序中采用的图的存储结构为邻接表，对于有向

图，一条弧将存储一个弧结点，对于无向图，一条弧将存储两条弧结点; 5、 测试数据：

（1）、Graph1.txt 8 9 1

A B C D E F G H A B A C B D B E C F C G E H G F H D

ABDEH（2）Graph2.txt 7 6 1

A B C D E F G A C B A C B D E D F E

CFG

ABDEF（3）Graph3.txt 9 8 0

A B C D E F G H I A B B C B H D H E H F H

CG

G H I H

IFHDAB

GEC（4）Graph4.txt 11 12 0

A B C D E F G H I J K A B A D B C

C D E J E K F G F K G H H K I J I K

DABIJE二、 概要设计

1、 图的邻接表的定义

struct ArcNode//弧结点的定义 {

CFKH

G int adjvex;//邻接点的位置 ArcNode * nextarc;//下一条弧 };

struct VNode//顶点结点的定义 {

char data;//该顶点的数据域，这里简化为一个字符 bool visited;//是否被访问的标志域，0未访问，1已访问 ArcNode * firstarc;//指向第一条以该顶点为出发点的弧//的指针域 };

struct AlGraph//定义邻接表表示的图的数据结构 {

VNode vexs[MAXSIZE];//顶点向量 int arcnum;//弧的数目 int vexnum;//顶点的数目

bool isDirected;//是否为有向图的标志域,1为有向，0为无//向 };

2、 图的邻接表创建模块

Status createAlGraph(AlGraph & g,string file) 初始条件:file所指文件路径是正确的

参数:g传入要创建的邻接表，file传入图的数据所在文件 操作结果:创建一个邻接表

int locateVex(AlGraph g,char vexdata) 初始条件:邻接表g已经初始化

参数:g传入图的邻接表，vexdata传入顶点字符数据， 操作结果:返回所查询顶点在邻接表的顶点向量中的位置， 若查询失败，返回-1

Status addArc(AlGraph & g,int from,int to)

初始条件:邻接表g已经初始化，from所指顶点位置合法， to所指顶点位置合法

参数:g传入图的邻接表，from传入起点的位置，to传入终

点的位置

操作结果:在邻接表中添加一条弧，如果是双向图，将通过

添加2条弧来表示无向边

3、深度优先遍历和广度优先遍历模块

void DFS(AlGraph & g,int v ,vector& edges) 初始条件: g已经初始化，v所指顶点位置存在

参数: g传入图的邻接表，v传入深度优先搜索的起点位置， edges传入用来存储生成树的边的向量 操作结果: 从v位置的顶点递归地深度优先搜索图 void DFSVisit(AlGraph & g,int & count) 初始条件: g已经初始化

参数: g传入图的邻接表，count传入深度优先搜索使用的

次数计数器

操作结果: 对整个图进行深度优先遍历

void BFS(AlGraph & g,int v, vector& edges) 初始条件: g已经初始化，v所指顶点位置存在

参数: g传入图的邻接表，v传入广度优先搜索的起点位置 edges 传入用来存储生成树边的向量 操作结果: 从v位置的顶点递归地广度优先搜索图 void BFSVisit(AlGraph & g,int & count) 初始条件: g已经初始化

参数: g传入图的邻接表，count传入广度优先搜索使用的

次数计数器

操作结果: 对整个图进行广度优先遍历

三、 详细设计

1、 图的邻接表创建模块

Status createAlGraph(AlGraph & g,string file)

{

ifstream is(file.c_str());

is>>g.vexnum>>g.arcnum;//读入定点数和弧的数目 int isDirected=false; is>>isDirected;

g.isDirected=isDirected==1?true:false;//读入图是否为有向图的标志 cout<<\文件\<

cout<<\顶点数目:\<

if(g.vexnum<0||g.arcnum<0)//如果读入的顶点个数和弧的条数数值错误，返回错误

{

cout<<\顶点数为负数\\n\; return ERROR; }

if(g.vexnum>50)

return OVERFLOW; printf(\顶点有：\);

for(int i=0;i

is>>g.vexs[i].data;

printf(\,g.vexs[i].data); while(!isAlpha(g.vexs[i].data)) is>>g.vexs[i].data; g.vexs[i].visited=false; g.vexs[i].firstarc=NULL; }

printf(\); int from,to; char fc,tc; printf(\弧：\);

for(int i=0;i

is>>fc;

while(!isAlpha(fc)) is>>fc; is>>tc;

printf(\,fc,tc); while(!isAlpha(tc)) is>>tc;

from=locateVex(g,fc); to=locateVex(g,tc); if(from<0||to<0) return ERROR; addArc(g,from,to);

if(!g.isDirected)//若是无向图，再添加一条逆指的弧 addArc(g,to,from); }

printf(\);

ArcNode * iter=NULL;

for(int i=0;i

printf(\点%c的邻接点依次为：\,g.vexs[i].data); iter=g.vexs[i].firstarc; while(iter)

{

printf(\,g.vexs[iter->adjvex].data); iter=iter->nextarc; }

printf(\); }

printf(\创建成功！\\n\); return OK; }

其中调用了addArc和locateVex函数可以参见源文件中的具体实现代码

2、 深度优先遍历和广度优先遍历模块

void DFS(AlGraph & g,int v，vector edges) {

g.vexs[v].visited=true;//先访问当前结点 printf(\,g.vexs[v].data);

ArcNode * iter=g.vexs[v].firstarc; Edge e;

while(iter) {

if(!g.vexs[iter->adjvex].visited)

{//若其邻接点没有被访问，递归地//对其邻接点进行深度优先搜索 e.from=g.vexs[v].data;

e.to=g.vexs[iter->adjvex].data;

edges.push_back(e);//将新探索的弧加入生成树的边集 DFS(g,iter->adjvex); iter=iter->nextarc; } } }

void BFS(AlGraph & g,int v，vector edges) {

queue bsq;//创建一个辅助队列来实现广度优先搜索 Edge e;

bsq.push(v);//这里要注意一点，所有要进队的结点必须先访问再进队，否//则若有已入队结点可能由于未被访问而被再次入队 g.vexs[v].visited=true;//先访问当前结点 ArcNode * iter=NULL; while(!bsq.empty())

{

//cout<<\访问到\ printf(\,g.vexs[bsq.front()].data); e.from=g.vexs[bsq.front()].data; iter=g.vexs[bsq.front()].firstarc; bsq.pop(); while(iter) {

if(!g.vexs[iter->adjvex].visited)//若邻接点未被访问 {

e.to=g.vexs[iter->adjvex].data;

edges.push_back(e);//将新探索到的弧加入生成树的边集 g.vexs[iter->adjvex].visited=true;//访问邻接点并将邻接//点入队

bsq.push(iter->adjvex); }

iter=iter->nextarc;//继续询问下一个邻接点

} } }

四、 调试分析

1、 设计图的数据结构的起初没有考虑到图的2种类

型（有向和无向）,只考虑了有向图的遍历，之后发现程序不能处理无向图的时候，通过为图的数据结构添加一个用来标识图的有向无向的标志，并在算法中通过判断此标志来进行分别处理，使得程序的功能更加完善；

2、 在设计图的广度优先遍历时，用到了队列作为辅

助存储结构来帮助实现图的广度优先遍历，但这里出现一个逻辑错误，在对顶点入队前没有先将顶点的已访问属性设置，结果导致对于较复杂的

图的广度优先搜索时有的顶点被重复入队，通过改变为先访问，再入队，改正了这一个逻辑错误， 3、程序中发现的许多逻辑错误是通过用尽量多样的测试数据进行测试发现的，在本次试验中，我发现要对一个程序进行调试，并从中发现尽可能多的错误，测试数据要足够丰富，覆盖的情况比较多，这样才有利于发现逻辑错误。

五、 测试结果

1、 Graph1.txt

2、 Graph2.txt

3、 Graph3.txt

4、 Graph4.txt

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