已阅读5页,还剩48页未读, 继续免费阅读
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
7.3.2.连通图的广度优先遍历,1.广度优先遍历以x开始的连通图,访问X,且x入队列若队列不空,重复以下步骤取队头元素并放入v中考察v的各个邻接点,若未访问,则先访问,然后放在队列尾部返回步骤,算法描述:,2.算法演示,例图及其邻接表表示,演示开始,以v1为遍历的起点,队列,v1,访问v1,v1,队列,v1,V1入队列,v1,队列,v1,取队头元素,v1,队列,v1,v2,V1的邻接点v2没有被访问过,访问之,且入队列,v1,队列,v1,v2,v2,v1,队列,v1,v2,v2,v3,V1的邻接点v3没有被访问过,访问之,且入队列,v1,队列,v1,v2,v2,v3,v3,v1,队列,v2,v2,v3,v3,v1,队列,v2,v2,v3,v3,v1,队列,v2,v2,v3,v3,v1,队列,v2,v2,v3,v3,V2的邻接点v1已经被访问过不再访问,v1,队列,v2,v2,v3,v3,v4,V2的邻接点v4没有被访问过,访问之,且入队列,v1,队列,v2,v2,v3,v3,v4,v4,v1,队列,v2,v2,v3,v3,v4,v4,v5,V2的邻接点v5没有被访问过,访问之,且入队列,v1,队列,v2,v2,v3,v3,v4,v4,v5,v5,v1,队列,v2,v3,v3,v4,v4,v5,v5,v1,队列,v2,v3,v3,v4,v4,v5,v5,v1,队列,v2,v3,v3,v4,v4,v5,v5,v1,队列,v2,v3,v3,v4,v4,v5,v5,V3的邻接点v1已经被访问过不再访问,v1,队列,v2,v3,v3,v4,v4,v5,v5,v6,V3的邻接点v6没有被访问过,访问之,且入队列,v1,队列,v2,v3,v3,v4,v4,v5,v5,v6,v6,v1,队列,v2,v3,v3,v4,v4,v5,v5,v6,v6,v7,V3的邻接点v7没有被访问过,访问之,且入队列,v1,队列,v2,v3,v3,v4,v4,v5,v5,v6,v6,v7,v7,v1,队列,v2,v3,v4,v4,v5,v5,v6,v6,v7,v7,v1,队列,v2,v3,v4,v4,v5,v5,v6,v6,v7,v7,v1,队列,v2,v3,v4,v4,v5,v5,v6,v6,v7,v7,v1,队列,v2,v3,v4,v4,v5,v5,v6,v6,v7,v7,V4的邻接点v2已经被访问过不再访问,v1,队列,v2,v3,v4,v4,v5,v5,v6,v6,v7,v7,v8,V4的邻接点v8没有被访问过,访问之,且入队列,v1,队列,v2,v3,v4,v4,v5,v5,v6,v6,v7,v7,v8,v8,v1,队列,v2,v3,v4,v5,v5,v6,v6,v7,v7,v8,v8,v1,队列,v2,v3,v4,v5,v5,v6,v6,v7,v7,v8,v8,v1,队列,v2,v3,v4,v5,v5,v6,v6,v7,v7,v8,v8,V5的邻接点v2、v8已经被访问过不再访问,v1,队列,v2,v3,v4,v5,v6,v6,v7,v7,v8,v8,v1,队列,v2,v3,v4,v5,v6,v6,v7,v7,v8,v8,v1,队列,v2,v3,v4,v5,v6,v6,v7,v7,v8,v8,V6的邻接点v3、v7已经被访问过不再访问,v1,队列,v2,v3,v4,v5,v6,v7,v7,v8,v8,v1,队列,v2,v3,v4,v5,v6,v7,v7,v8,v8,v1,队列,v2,v3,v4,v5,v6,v7,v7,v8,v8,V7的邻接点v3、v6已经被访问过不再访问,v1,队列,v2,v3,v4,v5,v6,v7,v8,v8,v1,队列,v2,v3,v4,v5,v6,v7,v8,v8,V8的邻接点v4、v5已经被访问过不再访问,v1,队列,v2,v3,v4,v5,v6,v7,v8,队列为空,算法结束,3.算法实现,从演示过程可以看出,我们必须知道顶点是否已经被访问过。在具体实现时,我们用一个数组visited来记录顶点是否被访问过。如果visitedi的值为True,则顶点vi已经被访问,否则没有被访问。,3.算法实现,VoidBFS(GraphG,intx)Visited100=False;/假设图中顶点数没有超过100个Visitedx=True;coutx;Queue.push(x);While(!Q.empty()V=Queue.front();Queue.pop();For(v的每个邻接点w)If(visitedw=false)Visitedw=True;coutw;Queue.push(w);,当图的存储结构为邻接表时,广度优先算法可以表示如下:voidBFS(ALGraphmg,intx)boolvisited100=false;queueq;cout0;w=:NextAdjVex(mg,v,w)if(visitedw=false)coutmg.vexsw.data;visitedw=true;q.push(w);,练习题:对于下面一个图及其存储结构,写出以v2、v8为起始点的广度优先遍历序列。,例图及其邻接表表示,答
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 书写工具市场分析及投资价值研究报告
- 电脑打印机用墨带项目成效分析报告
- 春节物价调查表
- 相机镜头转接环项目成效分析报告
- 基于BIM的REVIT综合布线设计实例教程 课件 6 空调系统
- 航空氧气面罩产品相关项目实施方案
- 食品自动包装机产品商业计划书
- 空粉饼盒产品商业计划书
- 不含药物的梳洗制剂项目质量管理方案
- 泄油用非金属容器产品相关项目实施方案
- 《小飞侠彼得潘》阅读练习题(有答案,内容全)
- 四川省泸州市泸县名校2022-2023学年七年级下学期期末考试数学试题及参考答案
- 2023-2024学年广西壮族自治区南宁市小学语文四年级期末通关测试题详细参考答案解析
- AQXXXX金属非金属地下矿山监测监控系统建设规范
- 森林采伐作业规程(行标)
- 世界政治经济与国际关系知到章节答案智慧树2023年武汉科技大学
- 《稻花香酒业盈利能力分析报告(3200字)》
- RB/T 083-2022建筑供暖供冷系统能效评价规范
- 国内投资项目不予免税的进口商品目录3
- 监控系统维修保养记录表
- 高压旋喷桩施工工艺与施工方案
评论
0/150
提交评论