数据结构 第6章 图（一轮习题总结）
数据结构 第6章 图
- 6.1 图的基本概念
- 6.2 图的存储及基本操作
- 6.3 图的遍历
- 6.4 图的应用
6.1 图的基本概念（2 4 11）
6.2 图的存储及基本操作（1 12 13 15 16）
6.3 图的遍历（2 3 5 16）
6.4 图的应用
6.1 图的基本概念
- T2
一个有个顶点和n条边的图，一定是有环的。 - T4
无向图的连通分量 = 极大连通子图
图的遍历：每个结点只访问一次；若为非连通图，可能某顶点出不能完全访问。 - T6
完全无向图中，n个顶点，边=n(n-1)/2 - T11
极大连通子图：连通分量
极小连通分量：图的生成树
6.2 图的存储及基本操作
- T1
图的拓扑序列 / DAG图：一个有向图中不存在环
（对应的领接矩阵对角线以下元素全为0，图一定没有环，即图的拓扑序列一定存在，但拓扑序列不唯一）
拓扑排序的算法：
（1）从有向图中选择一个没有前驱（即入度为0）的顶点并输出。
（2）从网中删除该顶点，并删除从该顶点出发的全部的有向边。
（3）重复上述步骤，直到剩余网中不再存在没有前驱的顶点为止。 - T12
无向图没有自己指向自己的边
无向图的邻接表最多有n(n-1)个边表结点，每条边存储两边 - T15 T16
领接多重表——无向图（顶点结点：data firstedge；弧结点…）
十字链表——有向图：（顶点结点：data firstin firstout；弧结点…）
领接矩阵、领接表——无向图、有向图
6.3 图的遍历
- T1
广度优先可以解决各边权值相等的单源最短路径问题 - T2
在DFSTraverse函数中调用DFS函数的次数 = 连通分量数 - T3
DFS和BFS的时间复杂度以及空间复杂度都相等
（1）空间复杂度：O(n)；深度优先DFS—栈；广度优先BFS—队列
（2）时间复杂度：领接表O(n+e)；领接矩阵O(n2) - T5
深度优先遍历的注意点：若出现环，退回求下一个顶点（栈）
6.4 图的应用
相关文章：
数据结构 第6章 图（一轮习题总结）
数据结构 第6章 图 6.1 图的基本概念6.2 图的存储及基本操作6.3 图的遍历6.4 图的应用 6.1 图的基本概念（2 4 11） 6.2 图的存储及基本操作（1 12 13 15 16） 6.3 图的遍历（2 3 5 16） 6.4 图的应用 6.1 图的基…...
如何在智能交通系统中使用物联网技术提高道路安全和效率
在智能交通系统中，物联网（IoT）技术可以通过多种方式提高道路安全和效率。以下是利用物联网技术提高智能交通系统效能的具体方法： 1. 车与路、车与车通信（V2X）：通过在道路上部署传感器和路侧单元…...
七大 QC 工具图的定义与示例（看这篇就够了）
前言 七大 QC 工具图是通过数值的方式进行数据分析的工具，分别是鱼骨图、直方图、柏拉图、散布图、管制图、检查图和层别图。其实，我们在日常生活与工作中经常看到它们，只是样子和名字对不上而已，今天写这篇文章就是为了帮助自己…...
【JavaScript算法】DOM树层级显示
题目描述： 上述表达式的输出结果为 [DIV] [P, SPAN, P, SPAN] [SPAN, SPAN]直接上代码 let tree document.querySelector(".a"); function traverseElRoot(elRoot) {const result [];function traverse(element, level) {if (!result[level]) {resul…...
MySql实战--全局锁和表锁 ：给表加个字段怎么有这么多阻碍
今天我要跟你聊聊MySQL的锁。数据库锁设计的初衷是处理并发问题。作为多用户共享的资源，当出现并发访问的时候，数据库需要合理地控制资源的访问规则。而锁就是用来实现这些访问规则的重要数据结构。 根据加锁的范围，MySQL里面的锁大致可以分成…...
axios请求类型是文件流怎么显示报错信息
axios请求类型是文件流，但是报错信息的话没法显示，在request.js文件中更改一下request拦截器代码： service.interceptors.request.use(config > { ...... , error > { console.log(error, 报错报错) // 处理请求错误 if (error.respons…...
DataX 源码改造支持Mysql 8.X
文章目录 DataX 源码改造支持Mysql 8.X问题背景克隆源代码并修改重新打包生产环境发布DataX 源码改造支持Mysql 8.X 问题背景 今天在使用DataX同步数据的时候遇到一个问题，报错如下 错误信息为：java.sql.SQLException: No suitable driver found for ["jdbc:mysql://…...
大数据学习-2024/3/29-oracle使用介绍
在plsql中登录ORACLE数据。 默认用户： 1、sys： 角色：数据库超级管理员账户。 权限：具有最高的权限，可以执行任何操作，包括操作数据字典和控制文件。可以创建和删除数据库对象，授予和回收其他用户…...
Vim - 文本编辑器 Vi vs Vim
你是否应该在学习 Vim 之前先学习 Vi，这完全取决于您自己、您的要求以及您的具体目标和需求。Vim 是 Vi 的扩展、增强和改进版本，它包括 Vi 的所有功能以及许多附加功能。 简约： Vi 设计简约。先学习 Vi 可以让你对基础知识有扎实的了解&…...
SpringBoot 登录认证（二）
SpringBoot 登录认证（一）-CSDN博客 SpringBoot 登录认证（二）-CSDN博客 SpringBoot登录校验（三）-CSDN博客 HTTP是无状态协议 HTTP协议是无状态协议。什么又是无状态的协议？ 所谓无状态&…...
C#语言规范及特殊用法笔记
前言 记录在学习C#过程中遇到的知识点，会持续更新。 1. 常用数据类型结构的默认值 创建类的一个实例时，在执行构造函数之前，如果没给成员变量赋初始值，C#编译器将每一个成员变量初始化为默认值。虽然C#编译器为每个类型都设置了…...
Mysql数据库：日志管理、备份与恢复
目录 前言 一、MySQL日志管理 1、存放日志和数据文件的目录 2、日志的分类 2.1 错误日志 2.2 通用查询日志 2.3 二进制日志 2.4 慢查询日志 2.5 中继日志 3、日志综合配置 4、查询日志是否开启 二、数据备份概述 1、数据备份的重要性 2、备份类型 2.1 从物理与…...
kubernetes(K8S)学习（八）：K8S之常见部署方案
K8S之常见部署方案 一、普通部署二、滚动更新（Rolling update）三、蓝绿部署（Blue/Green Deployment）四、灰度发布（金丝雀发布） 常见的部署方案参考博文：常见部署方案：普通部署、滚动…...
《AIGC重塑金融：AI大模型驱动的金融变革与实践》
🌈个人主页: Aileen_0v0 🔥热门专栏: 华为鸿蒙系统学习|计算机网络|数据结构与算法 💫个人格言:“没有罗马,那就自己创造罗马~” #mermaid-svg-oBSlqt4Vga1he7DL {font-family:"trebuchet ms",verdana,arial,sans-serif;font-siz…...
【详解】运算放大器工作原理及其在信号处理中的核心作用
什么是运算放大器 运算放大器（简称“运放”）是一种放大倍数非常高的电路单元。在实际电路中，它常常与反馈网络一起组成一定的功能模块。它是一种带有特殊耦合电路和反馈的放大器。输出信号可以是输入信号的加法、减法、微分和积分等数学运算…...
银河麒麟V10：sudo: /usr/bin/sudo 必须属于用户 ID 0(的用户)并且设置 setuid 位
一、引起原因： sudo chmod -R 777 bin 修改了/usr/bin/sudo的权限，引发后续问题。 二、现象： sudo执行命令报错： sudo: /usr/bin/sudo 必须属于用户 ID 0(的用户)并且设置 setuid 位 三、解决方法（知道root密码&…...
Android 多层级列表实现
方法一： Element.java ： package com.chy.ydy.tools.treeutil; /*** TreeView 元素* */ public class Element {/** 文字内容 */private String contentText;/** 在tree中的层级 */private int level;/** 元素的id */private int id;/** 父元素的id */…...
柔数组的介绍
柔数组简单介绍 这个词你可能没有听过但是他的确是存在的。 1.在c99中结构中的最后⼀个元素允许是未知⼤⼩的数组，这就叫做『柔性数组』成员 2这就代表了它存在与结构体中，很重要的一点是，他只能是结构体的最后的一个成员，这是…...
跳槽多次未成功，问题源自何处？
众所周知，2023年市场很难！看着企业们纷纷裁员，甚至连内推这个后门都走不通！哪怕有面试，都是屡屡碰壁，你想清楚问题出在哪了吗？😭“求职不得，夜不能寐；三更半夜…...
Linux 操作系统 022-串口/U盘/共享文件夹
Linux 操作系统 022-串口/U盘/共享文件夹 本节关键字：Linux、centos、串口、U盘、共享文件夹 本节相关指令：echo、cat、mkdir、mount 1、串口 #(1) 查看串口是否可用，可以对串口发送数据比如： $ echo helloworld >/dev/ttyS…...
java题目9：100匹马驮100担货，大马一匹驮3担，中马一匹驮2担，小马两匹驮1担。计算大中小马的数目（HorsesPackGoods9）
每日小语 正是他的意图损坏了他的悟性。——《充足理由律的四重根》 思考 有点鸡兔同笼的感觉嗷， //100匹马驮100担货，大马一匹驮3担，中马一匹驮2担，小马两匹驮1担。计算大中小马的数目（public class HorsesPackGoo…...
操作系统OS Chapter1
操作系统OS 一、概念和功能1.概念2.功能3.目标 二、特征1.并发2.共享3.虚拟4.异步 三、发展四、运行机制五、中断和异常1.中断的作用2.中断的类型3.中断机制的原理 六、系统调用七、操作系统结构八、操作系统引导九、虚拟机 一、概念和功能 1.概念 操作系统（OS&…...
UE4_Mouse_Interaction——拖拽物体的实现
鼠标拖拽物体，效果如下图： 1、新建PlayerController,更名字为MI_PlayerController，双击打开并设置参数： 2、新建GameMode，更名为MI_Gameinfo。参数如下设置： 3、新建材质，更名为BasicAsset02.参…...
Tomcat配置https
前言：本文内容为实操记录，仅供参考！ 一、证书 CA证书申请下载不赘述了。 二、上传证书 进入tomcat根目录，conf同级目录下创建cert文件夹，并将证书两个文件上传到该文件夹； 三、编辑conf/server.xml文件 ① …...
Modelsim手动仿真实例
目录 1. 软件链接 2. 为什么要使用Modelsim 3. Modelsim仿真工程由几部分组成？ 4. 上手实例 4.1. 新建文件夹 4.2. 指定目录 4.3. 新建工程 4.4. 新建设计文件（Design Files） 4.5. 新建测试平台文件（Testbench Files&…...
AXI-Stream——草稿版
参考自哔站：FPGA IP之AXI4-Lite AXI4-Stream_哔哩哔哩_bilibili 信号 传输层级从小到大 包(----------transfer--transfer--------)------delay--------包(----------transfer--transfer--------) TKEEP和TSTRB共同决定了是哪种数据流...
【编码器应用】第一节-编码器从从原理到应用详解
概述： 本文内容为常用电机编码器概览，将为您重点介绍编码器大致分类，以及增量编码器与西门子设备的配置连接方式。 编码器简介 编码器是利用LED光源发出的透射光对码盘进行光电扫描，光电元件接收编码器轴旋转时产生的明暗交替变…...
瑞_23种设计模式_中介者模式
文章目录 1 中介者模式（Mediator Pattern）1.1 介绍1.2 概述1.3 中介者模式的结构1.4 中介者模式的优缺点1.5 中介者模式的使用场景 2 案例一2.1 需求2.2 代码实现 3 案例二3.1 需求3.2 代码实现 🙊 前言：本文章为瑞_系列专栏之《2…...
sqlite删除数据表
1.如何删除表 在SQLite中，删除表的SQL语句是DROP TABLE。如果你想要在Python中使用SQLite库（如sqlite3）来删除一个表，你可以按照以下步骤操作： 连接到SQLite数据库。创建一个cursor对象。执行DROP TABLE语句。提交事…...
Spring Boot简介及案例
文章目录 Spring Boot简介以下是一个简单的 Spring Boot Web 应用实例**步骤 1：创建 Spring Boot 项目****步骤 2：编写 RESTful 控制器****步骤 3：配置主类****步骤 4：运行并测试应用** Spring Boot简介 Spring Boot 是一个用于简…...