09_广度优先搜索_第1页
09_广度优先搜索_第2页
09_广度优先搜索_第3页
09_广度优先搜索_第4页
09_广度优先搜索_第5页
已阅读5页，还剩15页未读， 继续免费阅读

付费下载

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

广度优先搜索,1,数据结构与算法365特训营,2,广度优先搜索,知识点概述,广度优先搜索（BreadthFirstSearch，BFS），又称为宽度优先搜索，是最常见的图搜索方法之一。广度优先搜索是从某个顶点（源点）出发，一次性访问所有未被访问的邻接点，再依次从这些访问过邻接点出发，似水中涟漪，似声音传播，一层层地传播开来。广度优先遍历是按照广度优先搜索的方式对图进行遍历。,3,4,5,广度优先遍历秘籍,先被访问的顶点，其邻接点先被访问。,根据广度优先遍历秘籍，先来先服务，可以借助于队列实现。每个结点访问一次且只访问一次，因此可以设置一个辅助数组：visitedi=false，表示第i个顶点未访问；visitedi=true，表示第i个顶点已访问。,6,算法步骤,初始化图中所有顶点未被访问，初始化一个空队列。从图中的某个顶点v出发，访问v并标记已访问，将v入队；如果队列非空，则继续执行，否则算法结束；队头元素v出队，依次访问v的所有未被访问邻接点，标记已访问并入队。转向步骤3；,7,完美图解,8,完美图解,9,完美图解,10,完美图解,11,完美图解,12,完美图解,13,完美图解,广度优先生成树,14,实践练习,广度优先遍历,15,实践练习,广度优先遍历,16,算法实现,17,算法实现,18,算法实现,19,算法分析,基于邻接矩阵的BFS算法查找每个顶点的邻接点需要O(n)时间，一共n个顶点，总的时间复杂度为O(n2)，使用了一个辅助队列，最坏的情况下每个顶点入队一次，空间复杂度为O(n)。基于邻接表的BFS算法查找顶点vi的邻接点需要O(d(vi)时间，d(vi)为vi的出度（无向图为度），对有向图而言，所有顶点的出度之和等于边数e，对无向图而言，所有顶点的度之和等于2e，因此查找邻接点的时间复杂度为O(e)，加上初始化时间O(n)，总的时间复杂度为O(n+e)，使用了一个辅助队列，最坏的情况下每个顶点入队
人人文库> 全部分类> 教育资料 > 课件下载

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论