没有合适的资源?快使用搜索试试~ 我知道了~
首页图的广度遍历实验报 有流程图
本演示程序用Visual C++编写,从键盘输入,以用户指定的结点为起点,实现无向图广度遍历,并打印输出广度遍历结点访问顺序。 1、输入的形式和输入值的范围:非负整数。 2、输入顶点的数量限制:最大40个 3、输出的形式: 根据用户的选择输出所创建邻接表的内容,广度遍历出结果。将点的次序打印出来。 4、程序所能达到的功能: 根据用户所输入的顶点数、边数以及相对的顶点建立相应的邻接表,再根据邻接表对图进行广度遍历,并打印输出结果。
资源详情
资源推荐
实 验 报 告
课程: 数据结构 班级:
0921
姓
名:
学
号:
092109
成绩: 指导教师: 张岩 实验日期:
2011/5/20
实验密级: 无 预习程度: 实验时间:
15:30~18:00
仪器组次:
E13
必 修 / 选
修:
必修 实验序号: (三)
实验名称: 图的结构的应用
实验目的与要求:
编程将若干结点组成的无向图用邻接链表存入计算机,并广度遍历输出该图。
实验仪器:
名称 型号 数量
微机
DELL PP33L
1
一、实验要求:
编程将若干结点组成的无向图用邻接链表存入计算机,并广度遍历输出该
图。
二、需求分析:
本演示程序用 Visual C++编写,从键盘输入,以用户指定的结点为起点,实
现无向图广度遍历,并打印输出广度遍历结点访问顺序。
1、输入的形式和输入值的范围:非负整数。
2、输入顶点的数量限制:最大 40 个
3、输出的形式:
根据用户的选择输出所创建邻接表的内容,广度遍历出结果。将点的次序
打印出来。
4、程序所能达到的功能:
根据用户所输入的顶点数、边数以及相对的顶点建立相应的邻接表,再根
据邻接表对图进行广度遍历,并打印输出结果。
三、本次实验所需要的相关知识储备:
1 图的遍历介绍
1.1、基本概念
图的遍历: 图中某个顶点出发访问图中所有顶点,且使得每一顶点仅被访问
一次,这个过程称为图的遍历。图的遍历是从图中某个顶点出发,沿着某条搜
索路径对图中其余每个顶点进行访问, 并且使图中的每个顶点仅被访问一次的过
程。
图的遍历是图运算中最重要的运算,也是图的基本运算之一,图的许多运算都
是以遍历为基础的。
1.2、 分类
按 照搜 索 途径 的 不 同 , 图 的 遍 历 可 分 为 : 深 度 优 先遍 历 ( Depth-First
Traverse)和广度优先遍历(Breadth-First Traverse)两大类。深度优先遍历和广
度优先遍历是最为重要的两种遍历图的方法。
(1)深度优先遍历 (Depth-First Traverse)
特点:尽可能先对纵深方向的顶点进行访问
1 .深度优先遍历的递归定义
假设给定图 G 的初态是所有顶点均未曾访问过。在 G 中任选一顶点 v 为初始
出发点(源点),则深度优先遍历可定义如下:首先访问出发点 v,并将其标记为
已访问过;然后依次从 v 出发搜索 v 的每个邻接点 w。若 w 未曾访问过,则以
w 为新的出发点继续进行深度优先遍历,直至图中所有和源点 v 有路径相通的
顶点(亦称为从源点可达的顶点)均已被访问为止。若此时图中仍有未访问的顶
点,则另选一个尚未访问的顶点作为新的源点重复上述过程,直至图中所有顶
点均已被访问为止。
图的深度优先遍历类似于树的前序遍历。采用的搜索方法的特点是尽可能先对
纵深方向进行搜索。这种搜索方法称为深度优先搜索(Depth-First Search)。相应
地,用此方法遍历图就很自然地称之为图的深度优先遍历。
2 . 深度优先搜索的过程
a 基本思想:
首先访问图中某一个指定的出发点 Vi;
然后任选一个与顶点 Vi 相邻的未被访问过的顶点 Vj;
以 Vj 为新的出发点继续进行深度优先搜索,直至图中所有顶点均被访问过。
b 具体过程:
设 x 是当前被访问顶点,在对 x 做过访问标记后,选择一条从 x 出发的未
检测过的边(x,y)。若发现顶点 y 已访问过,则重新选择另一条从 x 出发的未检
测过的边,否则沿边(x,y)到达未曾访问过的 y,对 y 访问并将其标记为已访问
过;然后从 y 开始搜索,直到搜索完从 y 出发的所有路径,即访问完所有从 y
出发可达的顶点之后,才回溯到顶点 x,并且再选择一条从 x 出发的未检测过的
边。上述过程直至从 x 出发的所有边都已检测过为止。此时,若 x 不是源点,
则回溯到在 x 之前被访问过的顶点;否则图中所有和源点有路径相通的顶点(即
从源点可达的所有顶点)都已被访问过,若图 G 是连通图,则遍历过程结束,否
则继续选择一个尚未被访问的顶点作为新源点,进行新的搜索过程。
(2)广度优先遍历(Breadth-First Traverse):
特点:尽可能先从指定的出发点,横向地访问图中各个顶点。
1 .广度优先遍历的定义
在访问了起始点之后,首先依次访问起始点的各个邻接点,然后依次访问那些
顶点中未被访问过的邻接点.依此类推,直到所有被访问到的顶点的邻接点都被
访问过为止.
2 .广度优先搜索的过程
a 算法基本思想:
首先访问图中某一指定的出发点 Vi;
然后依次访问 Vi 的所有接点 Vi1,Vi2…Vit;
再次访问 Vi1,Vi2…,Vit 的邻接点中未经访问过的顶点,依此类推,直到
图中所有顶点均被访问为止。
b 具体过程:
从广度优先搜索遍历方法可知,先被访问的顶点的邻接点也被访问,即假设
顶点 V 在 W 之前被访问,那么顶点 V 的所有未经访问的邻接点也在顶点 W 的
所有未经访问的邻接点之前被访问。这样可以在广度优先遍历的算法中设置一
个队列结构,用以保存已访问过的顶点的序号,访问该顶点的所有未经访问的
顶点。
当需要广度优先遍历时,首先得初始化一个队列,并初始化其为一个空队列。
而且由于公共变量 visited 里的值可能会受到其他的变化 ,所以一开始就把所有
结点都定义为未访问,然后当其访问到哪个结点时再把相应的结点的 visited 设
置为 1,即已经访问。再用 visitvex 函数显示该结点已访问。然后再把该结点入
队。只要队不为空。就把队里的结点出队。并查找下一个结点,直到所有的结
点都已经访问完
四、概要设计:
·总体设计流程
1 图的初始化
定义图并初始化图
2.建立图的邻接表
3.图的遍历
1.图的深度优先搜索
2.图的广度优先搜索
·图的遍历的模块化
1.图的存储结构;
2.图的输入;
3.BFS 编码;
4.合理输出图。
1、基本的定义:
1.1 算法说明
数据类型及函数定义
定义图
typedef struct{
int V[M];
int R[M][M];
int vexnum;
}Graph;
创建图
void creatgraph(Graph *g,int n)
打印图的邻接矩阵
void printgraph(Graph *g)
访问顶点
void visitvex(Graph *g,int vex)
队列的基本操作
定义队列
typedef struct{
int V[M];
int front;
int rear;
}Queue;
判断队列是否为空
quempty(Queue *q)
入队操作
enqueue(Queue *q,int e)
出队操作
dequeue(Queue *q)
广度遍历
void BFSTraverse(Graph *g)
本程序包含四个模块:
主程序模块
void main ()
{
剩余16页未读,继续阅读
mc157175
- 粉丝: 1
- 资源: 3
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- zigbee-cluster-library-specification
- JSBSim Reference Manual
- c++校园超市商品信息管理系统课程设计说明书(含源代码) (2).pdf
- 建筑供配电系统相关课件.pptx
- 企业管理规章制度及管理模式.doc
- vb打开摄像头.doc
- 云计算-可信计算中认证协议改进方案.pdf
- [详细完整版]单片机编程4.ppt
- c语言常用算法.pdf
- c++经典程序代码大全.pdf
- 单片机数字时钟资料.doc
- 11项目管理前沿1.0.pptx
- 基于ssm的“魅力”繁峙宣传网站的设计与实现论文.doc
- 智慧交通综合解决方案.pptx
- 建筑防潮设计-PowerPointPresentati.pptx
- SPC统计过程控制程序.pptx
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功