图的遍历试验报告VIP

本文格式为Word版，下载可任意编辑——图的遍历试验报告数据结构试验报告计科101冯康202300814128

试验图的基本操作

一、试验目的及要求

1、使学生1、使学生可以稳定所学的有关图的基本知识。2、熟练把握图的存储结构。3、熟练把握图的两种遍历算法。基本要求：

以邻接表为存储结构，实现连通无向图的深度优先和广度优先遍历。以用户指定的结

点为起点，分别输出每种遍历下的结点访问序列。

二、算法描述

[问题描述]

对给定图，实现图的深度优先遍历和广度优先遍历。

由学生依据软件工程的测试技术自己确定。

四、试验报告要求

1、试验报告要依照试验报告格式规范书写。2、试验上要写出多批测试数据的运行结果。3、结合运行结果，对程序进行分析。

编程思路：

深度优先算法：计算机程序的一种编制原理，就是在一个问题出现多种可以实现的方法和技术的时候，应当优先选择哪个更适合的，也是一种普遍的规律思想，此种思想在运算的过程中，用到计算机程序的一种递归的思想。

度优先探寻算法：又称广度优先探寻，是最简便的图的探寻算法之一，这一算法也是好多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先探寻类似的思想。其别名又叫BFS，属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位址，完全地探寻整张图，直到找到结果为止。

以临接链表作为存储结构，结合其存储特点和上面两种算法思想，给出两种遍历步骤：（1）既然图中没有确定的开始顶点，那么可从图中任一顶点出发，不妨按编号的顺序，先从编号小的顶点开始。

中原工学院计算机学院

打印时间：2023-3-26下午21:03

第1页共4页

数据结构试验报告计科101冯康202300814128

（2）要遍历到图中所有顶点，只需屡屡调用从某一顶点出发遍历图的算法。所以，下面只考虑从某一顶点出发遍历图的问题。

（3）为了在遍历过程中便于区分顶点是否已经被访问，设置一个访问标志数组visited[n]，n为图中顶点的个数，其初值为0，当被访问过后，其值被置为1。

（4）这就是遍历次序的问题，图的遍历寻常有深度优先遍历和广度优先遍历两种方式，这两种遍历次序对无向图和有向图都适用。

1、深度优先遍历从图中某顶点v出发进行深度优先遍历的基本思想是：（1）访问顶点v；

（2）从v的未被访问的邻接点中选取一个顶点w，从w出发进行深度优先遍历；（3）重复上述两步，直至图中所有和v有路径相通的顶点都被访问到。2、广度优先遍历从图中某顶点v出发进行广度优先遍历的基本思想是：（1）访问顶点v；

（2）依次访问v的各个未被访问的邻接点v1，v2，……vk；

（3）分别从v1，v2，……vk出发依次访问它们未被访问的邻接点，并使“先被访问顶点的邻接点〞先于“后被访问顶点的邻接点〞被访问，直至图中所有与顶点v有路径的顶点都被访问到。广度优先遍历图是以顶点v为起始点，由近至远，依次访问和v有路径相通而且路径长度为1，2，……的顶点。为了使“先被访问顶点的邻接点〞先于“后被访问顶点的邻接点〞被访问，需设置队列存储访问的顶点。五附录

代码解析：

#defineMAXVEX100intvisited[MAXVEX];intn;

structedgenode{

intadjvex;//临接结点序号intinfo;//临接结点信息edgenode*next;

中原工学院计算机学院

};连接结点的存储类型

structvexnode{intdata;//结点信息intNo;edgenode*link;

打印时间：2023-3-26下午21:03

第2页共4页

数据结构试验报告

};数组结点类型

/*BFS遍历时所需存储类型*/structqueue{

计科101冯康202300814128

intfront,rear;edgenode**base;};

typedefvexnodeadjlist[MAXVEX];采用用户交换模式来创立临接链表：voidCreatGroup(adjlistprintf(\输入结点(n)个数和边(e)个数:\for(inti=0;i\\n\\t起点序号，终点序号：\cin>>s>>d;//表示弧由s指向dedgenode*p=newedgenode;

/*每一个点的临接结点没有顺序，为了插入p->adjvex便利每次插入结点都插入在临接表的首位置，这样后插入的结点反而在前面*/

p->adjvex=d;p->info=g[d].data;p->next=g[s].link;g[s].link=p;}}

voidDFS(adjlistg,intv){

visited[v]=0;printf(\遍历过的结点用visited[v]=0进行标记edgenode*p=g[v].link;//查找连接结点while(p){

if(visited[p->adjvex])

DFS(g,p->adjvex);p=p->next;}}

/*广度优先探寻法(类似于树的层次遍历法)*/voidBFS(adjlistg,intv){visited[v]=0;

printf(\queueQ;

edgenode*p=g[v].link;

Q.base=newedgenode*[MAXVEX];Q.front=Q.rear=0;Q.base[Q.rear++]=p;

while(Q.front!=Q.rear){

visited[Q.base[Q.front]->adjvex]=0;

printf(\while(p){

if(visited[p->adjvex])Q.base[Q.rear++]=p;

中原工学院计算机学院

打印时间：2023-3-26下午21:03

第3页共4页

数据结构试验报告计科101冯康202300814128

p=p->next;}

p=g[Q.base[++Q.front]->adjvex].link;}}

心得体会：

数据结构顾名思义讲求的是一种存储结构，一路走来先后学习了表、树，最终学习的是图，对于每种存储结构学习之初都会学习一些基本操作，而操作之中又以创立和遍历为最基本的操作，只有熟练把握了以后才能对其他操作进行研究和学习。

图的存储结构相比表和树都要繁杂，其操作过程也较难进行把握。仅仅是创立图的存储结构便分为矩阵、临接链表、十字链表等，对于每一种存储结构又分为有向与无向之分。然而，深度优