数据结构——6.3 图的遍历

6.3 图的遍历

一、概念

  1. 图的广度优先遍历

    1. 在这里插入图片描述

    2. 树的广度优先遍历（层序遍历）：不存在“回路”，搜索相邻的结点时，不可能搜到已经访问过的结点：

      1. 若树非空，则根节点入队

      2. 若队列非空，队头元素出队并访问，同时将该元素的孩子依次入队

      3. 重复②直到队列为空

    3. 图的广度优先遍历(Breadth-First-Search,BFS)：搜索相邻的顶点时，有可能搜到已经访问过的顶点

      1. 找到与一个顶点相邻的所有顶点

      2. 标记哪些顶点被访问过

      3. 需要一个辅助队列

    4. 上述图的广度优先遍历的缺陷：只能遍历连通图，非连通图无法遍历

    5. 改进的BFS算法：

      1. 遍历visited数组，如果该顶点未被访问，则调用BFS

      2. BFS执行完成，回到①，直到所有顶点都被访问过

      3. 结论：对于无向图，调用BFS函数的次数=连通分量数

      4. 空间复杂度:最坏情况，辅助队列大小为 o(V)

    6. 广度优先遍历时间复杂度来源：找点、找边

    7. 邻接矩阵存储的图:

      1. 访问 V个顶点需要O(V)的时间

      2. 查找每个顶点的邻接点都需要O(V)的时间，而总共有V个顶点

      3. 时间复杂度=O(V²)

    8. 邻接表存储的图:

      1. 访问V个顶点需要O(V)的时间

      2. 查找各个顶点的邻接点共需要O(E)的时间

      3. 时间复杂度= O(V+E)

    9. 广度优先生成树

      1. 广度优先生成树由广度优先遍历过程确定。由于邻接表的表示方式不唯一，因此基于邻接表的广度优先生成树也不唯一。

    10. 广度优先生成森林

      1. 对非连通图的广度优先遍历，可得到广度优先生成森林

    11. 在这里插入图片描述

  2. 图的深度优先遍历DFS

    1. 在这里插入图片描述

    2. 树的深度优先遍历——其一：树的先根遍历：不存在重复访问问题

    3. 图的深度优先遍历：存在重复访问问题——设置标记数组：栈

    4. 在这里插入图片描述

    5. 上述DFS存在的问题：无法遍历非连通图

    6. 改进：与BFS改进相似

    7. 复杂度分析

      1. 空间复杂度:来自函数调用栈，最坏情况，递归深度为O(V)

      2. 时间复杂度=访问各结点所需时间+探索各条边所需时间

    8. 邻接矩阵存：时间复杂度：O(V²)

    9. 邻接表存：时间复杂度O(V+E)

    10. 在这里插入图片描述

    11. 深度优先遍历序列唯一性与生成树个数

      1. 同一个图的邻接矩阵表示方式唯一，因此深度优先遍历序列唯一，深度优先生成树也唯一

      2. 同一个图邻接表表示方式不唯一，因此深度优先遍历序列不唯一，深度优先生成树也不唯一

  3. 图的遍历与图的连通性

    1. 对无向图进行BFS/DFS遍历

      1. 调用BFS/DFS函数的次数=连通分量数

      2. 对于连通图，只需调用1次 BFS/DFS

    2. 对有向图进行BFS/DFS遍历

      1. 调用BFS/DFS函数的次数要具体问题具体分析

      2. 若起始顶点到其他各顶点都有路径，则只需调用1次BFS/DFS 函数

      3. 对于强连通图，从任一结点出发都只需调用1次 BFS/DFS

    3. 在这里插入图片描述

二、理解

  1. 当各边的权值相等时，广度优先算法可以解决单源最短路径问题

  2. 图的广度优先遍历相当于树的层次遍历

  3. 广度优先遍历需要用到队列

  4. 深度优先遍历需要用到栈

  5. 图的深度优先遍历相当于树的先根遍历，广度优先相当于树的层次遍历

  6. 深度优先遍历可以判断图中是否存在环

  7. 使用DFS递归遍历无环有向图，在退出时递归输出相应的顶点，得到逆拓扑有序顶点序列

三、技巧

  1. n个顶点，e条边的图采用邻接表存储，

    1. BFS遍历时

      1. 时间复杂度：O(n+e)：顶点表每个点和边表每个边都要遍历一次

      2. 空间复杂度：O(n)：每个点都入一次队

    2. DFS遍历时

      1. 时间复杂度：O(n+e)：顶点表每个点和边表每个边都要遍历一次

      2. 空间复杂度：O(n)：每个点都入一次队

  2. 画图的深度优先生成树、广度优先生成树：

    1. 先根据题目信息把图画出来

    2. 根据深度优先路径或广度优先路径，把不在路径上的边删去，即为生成树

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/384577.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

CTFSHOW web 89-100

CTFSHOW web 89-100

这边建议去我的gitbook或者github看观感更好（图片更完整） github:https://github.com/kakaandhanhan/cybersecurity_knowledge_book-gitbook.22kaka.fun gitbook:http://22kaka.fun 🏈 CTFSHOW PHP特性 （1）WEB 89 ①代码解释 <?php/* # -*- coding: utf-8 -*- # @…
阅读更多...
DataBinding源码浅析---初始化过程

DataBinding源码浅析---初始化过程

作为Google官方发布的支持库&#xff0c;DataBinding实现了UI组件和数据源的双向绑定&#xff0c;同时在Jetpack组件中&#xff0c;也将DataBinding放在了Architecture类型之中。对于DataBinding的基础使用请先翻阅前两篇文章的详细阐述。本文所用代码也是建立在之前工程基础之…
阅读更多...
牛客周赛 Round 32 F.小红的矩阵修改【三进制状态压缩dp】

牛客周赛 Round 32 F.小红的矩阵修改【三进制状态压缩dp】

原题链接&#xff1a;https://ac.nowcoder.com/acm/contest/75174/F 时间限制&#xff1a;C/C 1秒&#xff0c;其他语言2秒 空间限制&#xff1a;C/C 262144K&#xff0c;其他语言524288K 64bit IO Format: %lld 题目描述 小红拿到了一个字符矩阵&#xff0c;矩阵中仅包含&q…
阅读更多...
STM32CubeMx+MATLAB Simulink串口输出实验，UART/USART串口测试实验

STM32CubeMx+MATLAB Simulink串口输出实验，UART/USART串口测试实验

STM32CubeMxMATLAB Simulink串口输出实验
阅读更多...
C# CAD交互界面-自定义面板集-查找定位（六）

C# CAD交互界面-自定义面板集-查找定位（六）

运行环境 vs2022 c# cad2016 调试成功 一、代码说明 1. 类成员变量声明&#xff1a; List<ObjectId> objectIds new List<ObjectId>(); // 用于存储AutoCAD实体对象的ObjectId列表 private static Autodesk.AutoCAD.Windows.PaletteSet _ps2; // 自定义浮动面板…
阅读更多...
Spring Boot 笔记 006 创建接口_注册

Spring Boot 笔记 006 创建接口_注册

1.1 由于返回数据都是以下这种格式&#xff0c;那么久再编写一个result实体类 报错了&#xff0c;原因是没有构造方法 可以使用lombok的注解自动生成&#xff0c;添加无参的构造器和全参的构造器 package com.geji.pojo;import lombok.AllArgsConstructor; import lombok.NoArg…
阅读更多...
《UE5_C++多人TPS完整教程》学习笔记2 ——《P3 多人游戏概念（Multiplayer Concept）》

《UE5_C++多人TPS完整教程》学习笔记2 ——《P3 多人游戏概念（Multiplayer Concept）》

本文为B站系列教学视频 《UE5_C多人TPS完整教程》 —— 《P3 多人游戏概念&#xff08;Multiplayer Concept&#xff09;》 的学习笔记&#xff0c;该系列教学视频为 Udemy 课程 《Unreal Engine 5 C Multiplayer Shooter》 的中文字幕翻译版&#xff0c;UP主&#xff08;也是译…
阅读更多...
【机器学习】卷积和反向传播

【机器学习】卷积和反向传播

一、说明 自从 AlexNet 在 2012 年赢得 ImageNet 竞赛以来&#xff0c;卷积神经网络 (CNN) 就变得无处不在。从不起眼的 LeNet 到 ResNets 再到 DenseNets&#xff0c;CNN 无处不在。 您是否想知道 CNN 的反向传播中会发生什么&#xff0c;特别是反向传播在 CNN 中的工作原理。…
阅读更多...
蓝牙BLE学习-概述

蓝牙BLE学习-概述

1. 简介 1.1 蓝牙发展历程 蓝牙&#xff0c;直接来自于一位国王的名字--King Harald ‘Bluetooth Gromsson。这位国王因两件事留名于史&#xff0c;其一是在公园958年统一了丹麦和挪威&#xff0c;其二是在其死后&#xff0c;其牙齿呈现出暗蓝色的颜色&#xff0c;因而得名蓝牙…
阅读更多...
WordPress修改所有用户名并发送邮件通知的插件Easy Username Updater

WordPress修改所有用户名并发送邮件通知的插件Easy Username Updater

前面跟大家介绍了『如何修改WordPress后台管理员用户名&#xff1f;推荐2种简单方法』一文&#xff0c;但是对于有很多用户的站长来说&#xff0c;操作有点复杂&#xff0c;而且无法发邮件通知对方&#xff0c;所以今天boke112百科向大家推荐一款可以直接在WordPress后台修改所…
阅读更多...
记录一下，我使用stm32实现pwm波输入，以及对频率和占空比的计算，同时通过串口输出（实现-重要）

记录一下，我使用stm32实现pwm波输入，以及对频率和占空比的计算，同时通过串口输出（实现-重要）

1&#xff0c;首先看下半物理仿真 看下我的配置&#xff1a; 看下计算方法以及matlab的仿真输出的数据&#xff1a; timer3的ch2是选择高电平&#xff0c;计算频率 timer3的ch1是选择的是低电平&#xff0c;用来计算周期 其中TemPIpre表示的是CH2输出的值&#xff0c; TemPI…
阅读更多...
ElasticSearch级查询Query DSL上

ElasticSearch级查询Query DSL上

目录 ES高级查询Query DSL match_all 返回源数据_source 返回指定条数size 分页查询from&size 指定字段排序sort 术语级别查询 Term query术语查询 Terms Query多术语查询 exists query ids query range query范围查询 prefix query前缀查询 wildcard query通…
阅读更多...
「计算机网络」数据链路层

「计算机网络」数据链路层

数据链路层的地位&#xff1a;网络中的主机、路由器等都必须实现数据链路层信道类型 点对点信道&#xff1a;使用一对一的点对点通信方式广播信道 使用一对多的广播通信方式必须使用专用的共享信道协议来协调这些主机的数据发送 使用点对点信道的数据链路层 数据链路和帧 链…
阅读更多...
ansible shell模块 可以用来使用shell 命令 支持管道符 shell 模块和 command 模块的区别

ansible shell模块 可以用来使用shell 命令 支持管道符 shell 模块和 command 模块的区别

这里写目录标题 说明shell模块用法shell 模块和 command 模块的区别 说明 shell模块可以在远程主机上调用shell解释器运行命令&#xff0c;支持shell的各种功能&#xff0c;例如管道等 shell模块用法 ansible slave -m shell -a cat /etc/passwd | grep root # 可以使用管道…
阅读更多...
比特币突然大涨

比特币突然大涨

作者&#xff1a;秦晋 2月9日&#xff0c;除夕夜&#xff0c;比特币突然大涨&#xff0c;最高涨至48219美元&#xff0c;涨幅超6%。据CNBC报道&#xff0c;本周比特币已经上涨10.76%&#xff0c;创下自12月8日以来的最佳的一周。本周ETH上涨8.46%&#xff0c;成为自1月12日以来…
阅读更多...
蓝桥杯-X图形

蓝桥杯-X图形

问题描述 给定一个字母矩阵。一个 X 图形由中心点和由中心点向四个 45度斜线方向引出的直线段组成&#xff0c;四条线段的长度相同&#xff0c;而且四条线段上的字母和中心点的字母相同。 一个 X 图形可以使用三个整数 r,c,L 来描述&#xff0c;其中 r,c 表示中心点位于第 r 行…
阅读更多...
【Java程序设计】【C00261】基于Springboot的休闲娱乐代理售票系统（有论文）

【Java程序设计】【C00261】基于Springboot的休闲娱乐代理售票系统（有论文）

基于Springboot的休闲娱乐代理售票系统&#xff08;有论文&#xff09; 项目简介项目获取开发环境项目技术运行截图 项目简介 这是一个基于Springboot的休闲娱乐代理售票系统 本系统分为系统功能模块、管理员功能模块以及用户功能模块。 系统功能模块&#xff1a;休闲娱乐代理…
阅读更多...
视频讲解：优化柱状图

视频讲解：优化柱状图

你好&#xff0c;我是郭震 AI数据可视化 第三集&#xff1a;美化柱状图&#xff0c;完整视频如下所示&#xff1a; 美化后效果前后对比&#xff0c;前&#xff1a; 后&#xff1a; 附完整案例源码&#xff1a; util.py文件 import platformdef get_os():os_name platform.syst…
阅读更多...
探索Redis特殊数据结构：Geospatial(地理位置)在实际中的应用

探索Redis特殊数据结构：Geospatial(地理位置)在实际中的应用

一、概述 Redis官方提供了多种数据类型&#xff0c;除了常见的String、Hash、List、Set、zSet之外&#xff0c;还包括Stream、Geospatial、Bitmaps、Bitfields、Probabilistic&#xff08;HyperLogLog、Bloom filter、Cuckoo filter、t-digest、Top-K、Count-min sketch、Confi…
阅读更多...
【开源】JAVA+Vue.js实现天然气工程业务管理系统

【开源】JAVA+Vue.js实现天然气工程业务管理系统

目录 一、摘要1.1 项目介绍1.2 项目录屏 二、功能模块三、使用角色3.1 施工人员3.2 管理员 四、数据库设计4.1 用户表4.2 分公司表4.3 角色表4.4 数据字典表4.5 工程项目表4.6 使用材料表4.7 使用材料领用表4.8 整体E-R图 五、系统展示六、核心代码6.1 查询工程项目6.2 工程物资…
阅读更多...
最新文章

Copyright @ 2022~2023