图的遍历实验报告

1、实验五 图的基本操作一、实验目的1、使学生可以巩固所学的有关图的基本知识。2、熟练掌握图的存储结构。3、熟练掌握图的两种遍历算法。二、实验内容问题描述对给定图，实现图的深度优先遍历和广度优先遍历。基本要求以邻接表为存储结构，实现连通无向图的深度优先和广度优先遍历。以用户指定的结点为起点，分别输出每种遍历下的结点访问序列。【测试数据】由学生依据软件工程的测试技术自己确定。三、实验前的准备工作1、掌握图的相关概念。2、掌握图的逻辑结构和存储结构。3、掌握图的两种遍历算法的实现。四、实验报告要求1、实验报告要按照实验报告格式规范书写。2、实验上要写出多批测试数据的运行结果。3、结合运行结果，对程序进

2、行分析。编程思路：深度优先算法：计算机程序的一种编制原理，就是在一个问题出现多种可以实现的方法和技术的时候，应该优先选择哪个更合适的，也是一种普遍的逻辑思想，此种思想在运算的过程中，用到计算机程序的一种递归的思想。 度优先搜索算法：又称广度优先搜索，是最简便的图的搜索算法之一，这一算法也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim 最小生成树算法都采用了和宽度优先搜索类似的思想。其别名又叫BFS，属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话 说，它并不考虑结果的可能位址，彻底地搜索整张图，直到找到结果为止。 以临接链表作为存储结构，结合

3、其存储特点和上面两种算法思想，给出两种遍历步骤：（1）既然图中没有确定的开始顶点，那么可从图中任一顶点出发，不妨按编号的顺序，先从编号小的顶点开始。（2）要遍历到图中所有顶点，只需多次调用 从某一顶点出发遍历图的算法。所以，下面只考虑从某一顶点出发遍历图的问题。（3）为了在遍历过程中便于区分顶点是否已经被访问，设置一个访问标志数组 visitedn，n为图中顶点的个数，其初值为0，当被访问过后，其值被置为1。（4）这就是遍历次序的问题，图的遍历通常有深度优先遍历和广度优 先遍历两种方式，这两种遍历次序对无向图和有向图都适用。1、深度优先遍历    从图中某顶点v出

4、发进行深度优先遍历的基本思想是：（1）访问顶点v；（2）从v的未被访问的邻接点中选取一个顶点w，从w出发进行深度优先遍历；（3）重复上述两步，直至图中所有和v有路径相通的顶点都被访问到。2、广度优先遍历    从图中某顶点v出发进行广度优先遍历的基本思想是： （1）访问顶点v；（2）依次访问v的各个未被访问的邻接点v1，v2，vk；（3）分别从v1，v2，vk出发依次访问它们未被访问的邻接点， 并使“先被访问顶点的邻接点”先于“后被访问顶点的邻接点”被访问，直至图中所有与顶点v有路径的顶点都被访问到。广度优先遍历图是以顶点v为起始点，由 近至远，依次访问和v有路径

5、相通而且路径长度为1，2，的顶点。为了使“先被访问顶点的邻接点”先于“后被访问顶点的邻接点”被访问，需设置队列存储 访问的顶点。代码解析：#define MAXVEX 100int visitedMAXVEX;int n;struct edgenode int adjvex;/临接结点序号 int info; /临接结点信息 edgenode*next;连接结点的存储类型struct vexnode int data;/结点信息 int No; edgenode*link;数组结点类型/*BFS遍历时所需存储类型*/struct queue int front,rear; edgenode*b

6、ase;typedef vexnode adjlistMAXVEX;采用用户交换模式来创建临接链表：void CreatGroup(adjlist&g,int&n) int e,s,d; printf("输入结点(n)个数和边(e)个数:"); cin>>n>>e; for(int i=0;i<n;i+)/创建结点数组 printf("n输入第%d个结点信息No=",i); scanf("%d",&gi.data); gi.link=NULL; /*建立临接链表，创建的是有向图*/

7、 for(int i=0;i<e;i+) printf("第%d条边=>nt起点序号，终点序号：",i+1); cin>>s>>d;/表示弧由s指向d edgenode*p=new edgenode; /*每一个点的临接结点没有顺序，为了插入p->adjvex方便每次插入结点都插入在临接表的首位置，这样后插入的结点反而在前面*/ p->adjvex=d; p->info=gd.data; p->next=gs.link; gs.link=p; void DFS(adjlist g,int v) visitedv=0

8、; printf("%d=>",v);/遍历过的结点用visitedv=0进行标记 edgenode*p=gv.link;/查找连接结点 while(p) if(visitedp->adjvex) DFS(g,p->adjvex); p=p->next; /*广度优先搜索法(类似于树的层次遍历法)*/void BFS(adjlist g,int v) visitedv=0; printf("%d=>",v); queue Q; edgenode*p=gv.link; Q.base=new edgenode*MAXVEX; Q

9、.front=Q.rear=0; Q.baseQ.rear+=p; while(Q.front!=Q.rear) visitedQ.baseQ.front->adjvex=0; printf("%d=>",Q.baseQ.front->adjvex); while(p) if(visitedp->adjvex) Q.baseQ.rear+=p; p=p->next; p=gQ.base+Q.front->adjvex.link; 心得体会：数据结构顾名思义讲求的是一种存储结构，一路走来先后学习了表、树，最后学习的是图，对于每种存储结构学习之初都会学习一些基本操作，而操作之中又以创建和遍历为最基本的操作，只有熟练掌握了以后才能对其他操作进行研究和学习。图的存储结构相比表和树都要复杂，其操作过程也较难进行掌握。仅仅是创建图的存储结构便分为矩阵、临接链表、十字