图的遍历实验报告

1、实验4 :图的扫描主题：图及其应用图的扫描班级：名称：学校编号：完成日期：1 .需求分析1 .问题描述：与图的操作有关的算法大多基于图的扫描操作。 试制了在连接的无向图表上演示访问所有节点操作的程序。2 .基本要求：以邻接表为记忆结构，实现连通无向图的深度优先和宽度优先遍历。 以用户指定的节点为起点，分别输出各种扫描下的节点访问序列和对应的生成树的边缘集。3 .测试数据：教科书图7.33。 暂时无视英里，出发点是北京。4 .实现提示：假设图表中的节点不超过30个，并且每个节点由一个编号表示(如果图表中有n个节点，则它们的编号分别为1、2、n )。 通过输入图的所有边输入图，各边一对一，可以对对

2、边的输入顺序施加某种限制。 请注意，生成树的边是有向边，端点的顺序不能反转。5 .选择内容：(1) .根据堆栈类型(自己的定义和实现)，用非递归算法实现深度优先遍历。(2) .把邻接表做成记忆构造，把深度优秀的老师和广度优秀的老师做成树，用凹陷的表和树印刷成树。2 .概要设计1 .为了实现上述功能，图的抽象数据类型是必要的。 抽象数据类型的定义如下ADT图形举止数据对象V:V是具有相同特性的数据元素的集合，称为顶点集。数据关系r :R=VRVR= | v，wv且P(v，w )表示从v到w的弧，谓词P(v，w )定义了弧的意思和信息 ADT图形2 .这个抽象数据类型的常数如下：#define T

3、RUE 1#define FALSE 0#define OK 1#define max_n 20 /最大顶点数typedef char VertexType20；类型枚举 DG，DN，AG，an 图形密钥；enum BOOLFalse，True；3 .树的结构类型如下：typedef struct弧节点和矩阵的类型PPS； /VRType是圆弧的类型。 图-0，1网-权重int *Info； /可以省略有关弧的信息的指针ArcCell，adj矩阵 max _ n max _ n ；typedef struct举止VertexType vexsmax_n； /顶点adj矩阵arcs； /邻接矩阵

4、int vexnum，arcnum； /顶点数、边数MGraph；/队列类型定义typedef int QElemType；类型结构qnode举止QElemType data；结构qnode * next；QNode、*QueuePtr；typedef struct举止队列ptr前端；队列ptr rear；链接队列；4 .本计划包括三个模块1 ) .主程序模块void main ()举止种树深度优先搜索扫描广泛的优先搜索以下2 ) .树模块实现树的抽象数据类型3 ) .扫描模块实现树的深度优先扫描和宽度优先扫描模块间的调用关系如下主模块木材模块横动模块3 .详细设计#包括 STD afx.h

5、#includeusing namespace std；#define TRUE 1#define FALSE 0#define OK 1#define max_n 20 /最大顶点数typedef char VertexType20；类型枚举 DG，DN，AG，an 图形密钥；enum BOOLFalse，True；typedef struct弧节点和矩阵的类型PPS； /VRType是圆弧的类型。 图-0，1网-权重int *Info； /可以省略有关弧的信息的指针ArcCell，adj矩阵 max _ n max _ n ；typedef struct举止VertexType vexsm

6、ax_n； /顶点adj矩阵arcs； /邻接矩阵int vexnum，arcnum； /顶点数、边数MGraph；/队列的类型定义typedef int QElemType；类型结构qnode举止QElemType data；结构qnode * next；QNode、*QueuePtr；typedef struct举止队列ptr前端；队列ptr rear；链接队列；/初始化队列int init queue (链路队列* q )举止返回确认；以下/判断队列是否为空int empty queue (链路队列q )举止PS (K.front=q.rear )返回真；else返回假；以下加入/行列i

7、nt enqueue (链路队列* q，qelementtypee )举止队列ptr p；p-data=e；p-next=NULL；(*Q).rear-next=p；(*Q).rear=p；返回确认；以下/离开队伍int dequeue (链路队列* q，qelementtype*e )举止队列ptr p；if (* q ).front=(* q ).rear )返回- 1；p=(*Q).front-next；*e=p-data；(*Q).front-next=p-next；if(*Q).rear=p )(*Q).rear=(*Q).front；删除p；返回确认；以下/*顶点向量中的顶点定位*

8、/intlocate(mgrapgraph，VertexType v )举止PS；for(i=0； iG.vexnumG.arcnum；请输入cout 顶点： for(k=0； kG.vexsk；for(i=0； 欢跃；欢跃；求出i=Locate(G，vi) j=Locate(G，vj) /vi和Vj的后缀g.arcs I .adj=1；g.arcs j .adj=1；以下以下第一次调整(m graph g，int V )/图g用邻接矩阵表示，下标求v顶点的第一个邻接点int i=0；while (I=g.vex num )返回- 1；电子返回I； 返回/v的第一个相邻点的下标以下int NextAdjVex(MGraph G，int V，int w ) /图g用邻接矩阵表示int i=w 1；while(i=G.vexnum )返回- 1； /V的w邻接点之后没有邻接点else返回I； 返回/v行w列之后的第一个非零元后缀以下int visited100； /*设置全局访问标志数组*/PS PS (PK图形g，PS v )从/编号v的顶点开始，通过深度优先搜索对图g进行扫描PS；visitedv=1；cout=0； w=下一个调整(g，v，w ) )举止PS (！