程序员经验分享-hwhale

数据结构笔记--图

2023-11-11

数据结构笔记--图

图

本章总结

考试不考十字链表和临界多重表，考试紫色的做要求，除了Dijkstra算法

在这里插入图片描述

图的概念

基本术语

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述在这里插入图片描述在这里插入图片描述在这里插入图片描述

抽象数据类型

在这里插入图片描述
大学表示集合，小写表示集合的元素

图的存储结构

在这里插入图片描述

邻接矩阵表示法（数组）

无向图

在这里插入图片描述

有向图

在这里插入图片描述

有权图

在这里插入图片描述

邻接矩阵的优缺点

在这里插入图片描述

代码实现

在这里插入图片描述在这里插入图片描述

邻接表表示法（链式）

结构

在这里插入图片描述

无向图

在这里插入图片描述

有向图

在这里插入图片描述
逆邻接表可以使求度更容易
在这里插入图片描述

邻接表的优缺点

在这里插入图片描述

邻接矩阵与邻接表的对比

在这里插入图片描述

代码实现

在这里插入图片描述

十字链表表示法（尚未自学）

用一个链表来表示邻接表与逆邻接表
在这里插入图片描述在这里插入图片描述在这里插入图片描述

邻接多重表

在这里插入图片描述

概念

邻接多重表(adjacent multiList)是无向图（网）的另一种链式存储结构。
在此存储结构中，
图的顶点信息存放在顶点数组中，数组元素有两个域：
data域：存放与顶点相关的信息；
firstedge域：指向一个单链表，此单链表存储所有依附于该顶点的边的信息。

这些单链表的一个表结点对应一条边，表结点有六个域：
mark：为标志域，用来标记该边是否被访问过；
ivex和jvex：分别存放该边两个顶点在图中的位置；
ilink：指向下一条依附于顶点ivex的边对应的表结点;
jlink：指向下一条依附于顶点jvex的边对应的表结点。
info：该域存放该边相关的信息，实际上就是弧的权值，对于无向图，info域可省略;

适宜应用（与邻接表对比）

决邻接表存储无向图时同一条边要存储两次的问题。
邻接多重表主要用于存储无向图。因为如果用邻接表存储无向图，每条边的两个边结点分别在以该边所依附的两个顶点为头结点的链表中，这给图的某些操作带来不便。例如，对已访问过的边做标记，或者要删除图中某一条边等，都需要找到表示同一条边的两个结点。因此，在进行这一类操作的无向图的问题中，采用邻接多重表作存储结构更为适宜。

图的遍历

基本概念

在这里插入图片描述

深度优先搜索

算法思路

在这里插入图片描述

邻接矩阵实现

在这里插入图片描述

在这里插入图片描述

邻接表实现

在这里插入图片描述在这里插入图片描述

两种方法效率分析

在这里插入图片描述

广度优先搜索

算法思路

在这里插入图片描述

邻接表实现

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

两种方法效率分析

在这里插入图片描述

图的其他运算

1、求图的生成树（或生成森林）

概念介绍

在这里插入图片描述

举例（生成树）

在这里插入图片描述

举例（生成森林）

在这里插入图片描述
在这里插入图片描述

2、求最小生成树

概念介绍

在这里插入图片描述
在这里插入图片描述

算法

在这里插入图片描述

Kruskal (克鲁斯卡尔)算法

1、不停的选最小的边进去，1->2->3->4->5，注意选边为5是不要构成环路
2、边是e条，但有个判断回路的过程，所以不是O（e）
在这里插入图片描述

Prim (普里姆)算法

先任选一个顶点，找最小的边，
这种算法无需判断回路
n为定点数
在这里插入图片描述

3、求最短路径

概念介绍（与最小生成树区分）

在这里插入图片描述

两种常见的最短路径问题:
单源最短路径-Dijkstra (迪杰斯特拉)算法

在这里插入图片描述

所有顶点间的最短路径一Floyd (弗洛伊德)算法

可以通过调用n次Dijkstra算法来完成，
时间复杂度为0(n3)
还有更简单的一一个算法: Floyd算法(略)

4、求关节点和重连通分量(略)

5、拓扑排序

6、求关键路径

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

2020数据结构学习

数据结构笔记--图 的相关文章

  • MoCo v1 论文笔记

    Momentum Contrast for Unsupervised Visual Representation Learning 论文笔记 DETR 论文笔记 Momentum Contrast for Unsupervised Visu

  • 三因素方差分析_【科研加油站】SPSS操作之三因素方差分析

    点击上方蓝字 轻松关注我们 以下内容转载自 医咖会 微信公众号 medieco ykh 作者Jane 上一期我们讨论了双因素方差分析 本期 科研加油站 栏目 我们一起来探讨三因素方差分析 问题与数据 某研究者想研究某类新药降低胆固醇水平的效

  • CData API Server全面且文档完整的API

    CData API Server全面且文档完整的API 使用现有业务信息创建API 连接到任何SQL以及NoSQL数据库以及API服务器 都会立即生成灵活 全面且文档完整的API 发现数据集成的潜力 API服务器API服务器提供了在企业AP

  • register的用法c语言,C语言中auto,static,register,extern存储类型的用法

    在C语言中提供的存储类型说明符有auto extern static register 说明的四种存储类别 四种存储类别说明符有两种存储期 自动存储期和静态存储期 其中auto和register对应自动存储期 具有自动存储期的变量在进入声明

  • Unity脚本API—Transform 变换

    场景中的每一个对象都有一个Transform 用于储存并操控物体的位置 旋转和缩放 每一个Transform可以有一个父级 允许你分层次应用位置 旋转和缩放 可以在Hierarchy面板查看层次关系 他们也支持计数器 enumerator

  • AGV调度系统/两阶段算法模拟源代码 地图建模

    多 AGV调度系统 两阶段算法模拟源代码 地图建模c openTCS1 AGV调度系统源码 OpenTCS OpenTCS是一个开源的AGV调度系统程序 能给初入AGV行业的人士一些帮助 该实例是包含源码的程序 可成功运行 2 openTC

  • UE4 蓝图数组反转节点ReverseforEachLoop的坑

    由于蓝图没有直接反转数组的节点类似于C 的reverse 所以只好用ReverseforEachLoop这个节点 但是这个节点有个坑 就是ArrayIndex是从数组末尾元素下标开始输出 并非是从0开始 因此如果要用到ArrayIndex得

  • 记录一次JVM发生OOM问题的解决，包括jvisualvm工具的使用，以及对GC的理解等

    目录 OOM原因分析 解决 利用hprof文件分析的步骤 结合jvisualvm工具 jvisualvm实时监控本地jvm jvisualvm实时监控远程jvm 对于JVM的GC理解 Minor GC Full GC 常用JVM参数配置 查

  • WIN32 资源

    首先解释一下句柄 win32中的句柄在数值上表示一个32位的数 用来标识应用程序 进程中不同对象以及同类对象中的不同实例 而所谓实例就是指被实例化的对象 实例化的过程就是通过类创建对象的过程 实例化对象的目地是为对象开辟内存空间 所以句柄是

  • Java - 常用类 - BigInteger 和 BigDecimal

    文章目录 BigInteger 和 BigDecimal 介绍 应用场景 BigInteger 和 BigDecimal 介绍 应用场景 BigInteger适合保存比较大的整型 BigDecimal适合保存精度更高的浮点型 小数 pack

  • 智能人机交互

    前言 随着移动机器人越来越多地走向实 际应用 需要提高机器人与人类之 间的协同水平 实现机器人与人类的共融 一 人机交互的三个级别 二 火星车的遥操作控制 火星车的遥操作控制 超大时延 地面团队将命令序列发至火 星车 如要求火星车往前行驶1

  • C# 进度条使用

    前言 介绍C 自带的Progressbar控件的调用方法 对程序运行的进度进行提示 内容 接下来 介绍进度条在Winform界面中具体的应用和步骤 在项目中新建一个Winform界面 上面放一个ProgressBar和label控件 默认命

  • SourceInsight4.0.0124中文版-黑色背景主题

    此背景目前只在SI 4 0 0124中文版试过 此黑色主题是自己改的 亲测可用 只适用于4 0 0124中文版 4 0 0124中文版 4 0 0124中文版 其他中文版的没试过 此主题不适用英文版 也没必要用在英文版 因为英文版本身已自带

  • 基于TensorFlow Lite实现的Android花卉识别应用

    介绍 本教程将在Android设备上使用TensorFlow Lite运行图像识别模型 具体包括 使用TensorFlow Lite Model Maker训练自定义的图像分类器 利用Android Studio导入训练后的模型 并结合Ca

  • QT怎么实现HTTP同步

    Qt 提供了 QNetworkAccessManager 类可以用于实现 HTTP 同步请求 使用该类可以很方便地实现同步的 HTTP 请求 并可以直接获取响应的内容 下面是一个示例代码 include

  • myeclipse中设置代码注释模板

    1 设置模板 文件 Files 注释标签 Title file name Package package name Description todo author user date date 类型 Types 注释标签 类的注释 Clas

  • VMware提示此主机支持Intel VT-x,但Intel VT-x处于禁用状态——解决方法

    虚拟机VMware提示此主机支持Intel VT x 但Intel VT x处于禁用状态 也就是需要开启Intel Virtualization Technology虚拟化技术 Intel VT x完整名称是Intel Virtualiza

  • python安装opencv出现如下错误：Could not find a version that satisfies the requirement cv2 (from versions: )

    如题所示在python中安装cv2库是提示不能找到满足需要的版本 我的环境配置是 pycharm anaconda3 对应的python版本是python3 6 之前想着在pycharm中直接安装的 即打开项目对应的解释器设置模块 然后安装

  • c++ max() 报错 error: no matching function for call to ‘max’

    先举个小例子哈 我要统计字符串数组中最长字符串的长度 include

随机推荐

  • js检测字段中首个字符是否为字母

    var sSrc w33333 var sASC sSrc charCodeAt 0 if sASC gt 65 sASC lt 90 sASC gt 97 sASC lt 122 代码 A Z的ascii码 bai65 90 a z的as

  • Mybatis框架的基本知识梳理

    Mybatis框架的基本知识梳理 一 原始JDBC开发存在的问题 import org junit Test import java math BigDecimal import java sql public class JdbcTest

  • JavaScript详解DOM和BOM(持续更新)

    目录 1 DOM简介 1 1什么是DOM 1 2DOM树 2 如何获取页面元素 2 1根据id获取 2 2根据标签名获取 2 3通过HTML5新增方法获取 ie9以上支持 2 3 1根据类名获取元素的集合 2 3 2querySelecto

  • 简单示例中的多平台Avalonia .NET Framework编程基本概念

    目录 介绍 关于Avalonia 本文的目的 本文的组织 示例代码 解释概念 视觉树 Avalonia 工具 逻辑树 附加属性 样式属性 直接属性 有关附加 样式和直接属性的更多信息 绑定 什么是Avalonia UI和WPF中的绑定以及为

  • 如何在Mac电脑上编译Unity项目至iOS simulator （ipad/iphone）

    如何将Unity项目编译成iOS app 并在虚拟的ipad或者iphone上运行呢 大体步骤分为三步 使用Unity生成 xcodeproj 文件 在Xcode中运行 simulator 通过Xcode编译 xcodeproj 文件 并安

  • Selenium Xpath定位唯一文本元素

    Selenium Xpath定位唯一文本元素 问题概述 现有一网页 已知唯一文本元素a 需要定位父级的同级元素b并抓取文本b text 如何实现 给出案例 tr title td style width 60px class 110084

  • 我想问一下猫狗大战中出现Attempted to use a closed Session.怎么解决

    import os import tensorflow as tf from time import time import VGG16 model as model 自己定义的 import utils 定义了我们所用到的功能函数 fro

  • 2021-07-16（Qt实现图片拖拽功能）

    关于如何使用Qt实现简单的图片拖拽及缩放功能 一 代码实现 二 相关函数的解释 三 代码原理解释 一 代码实现 首先直接放出相关代码 可以根据注释进行一定修改 以下为头文件的内容 ifndef MAINWINDOW H define MAI

  • c#之base和this关键字

    如有错误 欢迎补充

  • ROS主从机设置

    ROS支持多机互通 一台主机启动roscore 启动Master节点 多台从机直接可以运行其他节点 本文记录主从机配置 实现多机互通 查看本机IP地址 ifconfig 其中 enp2s0代表有线网卡 lo代表本地回环 wlp5s0代表无线

  • Sublime Text 3中文乱码问题的解决（最有效）

    Sublime Text 3中文乱码问题的解决 最有效 Sublime Text 3是很好的代码编辑器 没有之一 因为她的性感高亮代码配色 更因为它的小巧 但是它默认不支持GBK的编码格式 因此打开GBK的代码文件 如果里面有中文的话 就会

  • UI控件----ProgressBar进度条 实例总结

    ProgressBar提供了可以向用户展示当前任务的进度 完成效果如下 单击增加 减少进度可以调节进度 完成步骤一 layout的xml文件中activity main xml完成代码

  • LRU的实现

    题目内容 实现一个 LRUCache 类 三个接口 LRUCache int capacity 创建一个大小为 capacity 的缓存 get int key 从缓存中获取键为 key 的键值对的 value put int key in

  • 使用Elasticsearch 出现的拒绝连接

    pom 文件 spring elasticsearch jest uris http 192 168 124 142 9201 data elasticsearch cluster name elasticsearch cluster no

  • 应用向国产架构体系化迁移的三大难点及解决方案

    转载本文需注明出处 微信公众号EAWorld 违者必究 李航 国家信创战略背景下 信创产业从党政 金融等领域高速扩展到电信 制造 教育等更广阔的市场 01 信创工作要解决应用向国产架构体系化迁移的三大难点 保障全面落地 伴随近年来信创实践的

  • pandas.errors.ParserError: Error tokenizing data. C error: Expected 17 fields in line 112, saw 18

    pandas errors ParserError Error tokenizing data C error Expected 17 fields in line 112 saw 18 pandas 简介 pandas 读取csv文件 运

  • 数字化时代，如何从战略设计到架构来打造智慧银行？

    导语 随着人工智能 大数据 云计算等技术向纵深发展 数字化转型已成为银行发展的 必答题 调整战略规划和架构重组 加大信息科技投入 推进科技人才队伍建设 持续推出数字化产品 近年来 深化数字化转型 以科技赋能金融服务已成为不少银行的发力点 今

  • python环境变量配置

    python现在的版本 主要是python2和python3两个大版本 这两个版本有很大的不同 当我们在自己电脑上同时安装了python2 x和python3 x版本的解释器的时候 就需要对环境变量的配置进行一定的修改 大概解释一下 我对环

  • 什么是 前端&后端，始端&末端

    前端 后端 前端和后端是指不同的开发领域和技术 前端指的是用户可见的界面 比如网页 移动应用 游戏等 使用的技术包括HTML CSS JavaScript等 后端指的是用户看不见的部分 比如服务器 数据库 业务逻辑等 使用的技术包括Java

  • 数据结构笔记--图

    数据结构笔记 图 图 本章总结 图的概念 基本术语 抽象数据类型 图的存储结构 邻接矩阵表示法 数组 无向图 有向图 有权图 邻接矩阵的优缺点 代码实现 邻接表表示法 链式 结构 无向图 有向图 邻接表的优缺点 邻接矩阵与邻接表的对比 代码

热门标签