实验7图的遍历.doc

青 岛 理 工 大 学 数据结构课程实验报告 数据结构 班级 软件112 实验日期 2013-5-20 姓名 何金荣 学号 201107225 实验成绩 实验名称 实验四 图的遍历（深度，广度） 实 验 目 的 及 要 求 （1） 通过此次实验巩固所学的有关图的基本知识。 （2） 熟练掌握图的逻辑结构和存储结构，以及图的其他基本操作。 （3） 熟练掌握图的邻接表存储及其基本操作。 （4） 熟练掌握图的深度优先遍历和广度优先遍历。 实 验 环 境 硬件平台：普通的PC机 软件平台：Windows XP操作系统 实 验 内 容 深度优先遍历： 从图中某顶点v出发进行深度优先遍历的基本思想是：? （1）访问顶点v；? （2）从v的未被访问的邻接点中选取一个顶点w，从w出发行深度优先遍历；? （3）重复上述两步，直至图中所有和v有路径相通的顶点都访问到。 广度优先遍历： 从图中某顶点v出发进行广度优先遍历的基本思想是：?? （1）访问顶点v；? （2）依次访问v的各个未被访问的邻接点v1，v2，……vk；? （3）分别从v1，v2，……vk出发依次访问它们未被访问的邻接点，?并使“先被访问顶点的邻接点”先于“后被访问顶点的邻接点”被访问，直至图中所有与顶点v有路径的顶点都被访问到。广度优先遍历图是以顶点v为起始点，由?近至远，依次访问和v有路径相通而且路径长度为1，2，…… 的顶点。为了使“先被访问顶点的邻接点”先于“后被访问顶点的邻接点”被访问，需设置队列存储?访问的顶点。 以邻接表为存储结构，实现无向图的深度优先遍历和广度优先遍历，以任意一结点为起点，分别输出每种遍历下的结点访问序列。 算 法 描 述 及 实 验 步 骤 实验步骤： 在实验前，在自己脑海中形成一个框架，掌握图的相关概念，以及图的基本知识。 以邻接表为存储结构，实现邻接表的数据结构以及各个存储算法。 采用邻接表存储结构，创建一个五相关信息的图或网G 通过输入一个图，能通过深度优先和广度优先遍历两种方法遍历出来。 算法描述： *******************邻接表的存储表示********************** #define MAX_VERTEX_NUM 20 typedef enum{DG,DN,UDG,UDN}GraphKind; /* {有向图,有向网,无向图,无向网} */ typedef struct /* 加 */ { int adjvex; /* 该弧所指向的顶点的位置 */ InfoType *info; /* 网的权值指针 */ }ElemType; typedef struct ArcNode /* 改 */ { ElemType data; /* 除指针以外的部分都属于ElemType */ struct ArcNode *nextarc; /* 指向下一条弧的指针 */ }ArcNode; /* 表结点 */ typedef struct { VertexType data; /* 顶点信息 */ ArcNode *firstarc; /* 第一个表结点的地址,指向第一条依附该顶点的弧的指针 */ }VNode,AdjList[MAX_VERTEX_NUM]; /* 头结点 */ typedef struct { AdjList vertices; int vexnum,arcnum; /* 图的当前顶点数和弧数 */ GraphKind kind; /* 图的种类标志 */ }ALGraph; #define LNode ArcNode /* 加，定义单链表的结点类型是图的表结点的类型 */ #define next nextarc /* 加，定义单链表结点的指针域是表结点指向下一条弧的指针域 */ typedef ArcNode *LinkList; /* 加，定义指向单链表结点的指针是指向图的表结点的指针 */ ********************队列的存储表示********************** /* 单队列的链式存储 */ typedef struct QNode { QElemType data; struct QNode *next; }QNode,*QueuePtr; typedef struct { QueuePtr front,rear; /* 对头和队尾指针 */ }LinkQueue; void EnQueue(LinkQueue *Q,QElemType e) { /*插入元素为队头的新元素 */ QueuePtr p