数据结构 第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 从物理与…...
学习（八）：K8S之常见部署方案)
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…...
Spring AI + DeepSeek 实战：5分钟搞定一个能听懂人话的数据库查询工具
Spring AI DeepSeek 实战：5分钟搞定一个能听懂人话的数据库查询工具 在数据驱动的时代，数据库查询是每个开发者绕不开的日常任务。但当你面对产品经理频繁变更的需求，或是运营同事临时提出的数据提取请求时，反复编写和调试SQL语句…...
从零构建：基于FreeRTOS与LVGL的低功耗智能手表实战指南
1. 项目背景与核心目标 第一次接触智能手表开发是在三年前，当时市面上开源的方案要么功能简陋，要么功耗高得离谱。作为一个嵌入式老鸟，我决定自己动手搞一套真正可用的低功耗方案。经过多次迭代，最终选择了FreeRTOSLVGL这个黄金组…...
PDF-Parser-1.0一键部署教程：5分钟搞定文档解析神器，小白也能轻松上手
PDF-Parser-1.0一键部署教程：5分钟搞定文档解析神器，小白也能轻松上手 1. 为什么你需要这个文档解析工具？ 你是不是经常遇到这样的烦恼？ 下载了一份重要的PDF报告，想把里面的表格数据整理到Excel里，结果…...
Phi-3-mini-128k-instruct与STM32开发：生成嵌入式C代码与调试逻辑
Phi-3-mini-128k-instruct与STM32开发：生成嵌入式C代码与调试逻辑 1. 引言 如果你玩过STM32，尤其是像STM32F103C8T6这种经典的“蓝色药丸”最小系统板，肯定对下面这些场景不陌生：为了点亮一个LED，翻遍数据手册&#…...
C盘清理与优化：为Realistic Vision V5.1模型文件腾出空间
C盘清理与优化：为Realistic Vision V5.1模型文件腾出空间 你是不是也遇到过这种情况：电脑C盘突然飘红，系统提示空间不足，想下载个新的AI模型，比如最近很火的Realistic Vision V5.1，却发现根本没地方放。看…...
先整个经典的入门款耶路撒冷十字电阻吸波器玩吧，就冲5.8GHz的WiFi频段调——毕竟现在连吸波材料都得先蹭蹭网络信号的热度才好入门嘛
CST仿真吸波器选5.8GHz有个小小心思：单层电阻超材料的谐振频率一般和单元边长相关，大概是谐振波长的0.2-0.4倍（等效介电常数εr算进去的话还要除以√εr的平方根），用的FR-4基板ε_r4.4、tanδ0.025、厚度1mm࿰…...
IDEA插件开发实战：手把手教你开发首个效率工具（附GitHub源码）
IDEA插件开发实战：从零打造你的专属效率工具 JetBrains系列IDE的强大之处不仅在于其核心功能，更在于其开放的插件生态系统。作为一名Java开发者，你是否曾想过为IDEA添加一个能提升自己工作效率的专属工具？本文将带你从零开始&…...
CST仿真设计：反射透射性线圆转换与线线转换实战案例及录屏教程
cst仿真设计 反射透射性线圆转换，线线转换 案例与录屏打开CST刚打开模板栏是不是总盯着默认的几个空模板发呆？今天咱们整点新手入门但能快速装逼朋友圈或者中期报告材料的活——反射透射都能玩的偏振转换超表面（Metasurface）&…...
突破VMware限制：在非苹果硬件上构建macOS开发环境完全指南
突破VMware限制：在非苹果硬件上构建macOS开发环境完全指南 【免费下载链接】unlocker 项目地址: https://gitcode.com/gh_mirrors/unloc/unlocker 实现跨平台macOS体验：VMware Unlocker核心价值解析 当开发者需要在Windows或Linux工作站上构建m…...
突破远程桌面限制：RDP Wrapper实现多用户并发连接的创新解决方案
突破远程桌面限制：RDP Wrapper实现多用户并发连接的创新解决方案 【免费下载链接】rdpwrap RDP Wrapper Library 项目地址: https://gitcode.com/gh_mirrors/rd/rdpwrap 副标题：适用于Windows Vista至Windows 11全版本的远程桌面功能扩展工具 在…...