当前位置: 首页 > news >正文

​​​【收录 Hello 算法】9.4 小结

目录

9.4   小结

1.   重点回顾

2.   Q & A


9.4   小结

1.   重点回顾

  • 图由顶点和边组成,可以表示为一组顶点和一组边构成的集合。
  • 相较于线性关系(链表)和分治关系(树),网络关系(图)具有更高的自由度,因而更为复杂。
  • 有向图的边具有方向性,连通图中的任意顶点均可达,有权图的每条边都包含权重变量。
  • 邻接矩阵利用矩阵来表示图,每一行(列)代表一个顶点,矩阵元素代表边,用 1 或 0 表示两个顶点之间有边或无边。邻接矩阵在增删查改操作上效率很高,但空间占用较多。
  • 邻接表使用多个链表来表示图,第 𝑖 个链表对应顶点 𝑖 ,其中存储了该顶点的所有邻接顶点。邻接表相对于邻接矩阵更加节省空间,但由于需要遍历链表来查找边,因此时间效率较低。
  • 当邻接表中的链表过长时,可以将其转换为红黑树或哈希表,从而提升查询效率。
  • 从算法思想的角度分析,邻接矩阵体现了“以空间换时间”,邻接表体现了“以时间换空间”。
  • 图可用于建模各类现实系统,如社交网络、地铁线路等。
  • 树是图的一种特例,树的遍历也是图的遍历的一种特例。
  • 图的广度优先遍历是一种由近及远、层层扩张的搜索方式,通常借助队列实现。
  • 图的深度优先遍历是一种优先走到底、无路可走时再回溯的搜索方式,常基于递归来实现。

2.   Q & A

Q:路径的定义是顶点序列还是边序列?

维基百科上不同语言版本的定义不一致:英文版是“路径是一个边序列”,而中文版是“路径是一个顶点序列”。以下是英文版原文:In graph theory, a path in a graph is a finite or infinite sequence of edges which joins a sequence of vertices.

在本文中,路径被视为一个边序列,而不是一个顶点序列。这是因为两个顶点之间可能存在多条边连接,此时每条边都对应一条路径。

Q:非连通图中是否会有无法遍历到的点?

在非连通图中,从某个顶点出发,至少有一个顶点无法到达。遍历非连通图需要设置多个起点,以遍历到图的所有连通分量。

Q:在邻接表中,“与该顶点相连的所有顶点”的顶点顺序是否有要求?

可以是任意顺序。但在实际应用中,可能需要按照指定规则来排序,比如按照顶点添加的次序,或者按照顶点值大小的顺序等,这样有助于快速查找“带有某种极值”的顶点。

相关文章:

​​​【收录 Hello 算法】9.4 小结

目录 9.4 小结 1. 重点回顾 2. Q & A 9.4 小结 1. 重点回顾 图由顶点和边组成,可以表示为一组顶点和一组边构成的集合。相较于线性关系(链表)和分治关系(树),网络关系(图&am…...

MYSQL数据库基础语法

目录 友情提醒第一章:数据库简述1)数据库简述2)常见的数据库软件3)MySQL数据库安装和连接4)SQL语句分类①DDL(Data Definition)②DML(Data Manipulation)③DQL&#xff0…...

R实验 参数检验(二)

实验目的:掌握正态分布和二项分布中,功效与样本容量之间的关系;学会利用R软件完成一个正态总体方差和两个正态总体方差比的区间估计和检验。 实验内容: (习题5.28)一种药物可治疗眼内高压,目的…...

【Linux】进程信号及相关函数/系统调用的简单认识与使用

文章目录 前言一、相关函数/系统调用1. signal2. kill3. abort (库函数)4. raise (库函数)5. alarm 前言 现实生活中, 存在着诸多信号, 比如红绿灯, 上下课铃声…我们在接收到信号时, 就会做出相应的动作. 对于进程也是如此的, 进程也会收到来自 OS 发出的信号, 根据信号的不同…...

Spring (14)什么是Spring Boot

Spring Boot是一个开源的Java基础框架,旨在简化Spring应用的创建和开发过程。Spring Boot通过提供一套默认配置(convention over configuration),自动配置和启动器(starters)来减少开发者的开发工作量和配置…...

区间预测 | Matlab实现CNN-KDE卷积神经网络结合核密度估计多置信区间多变量回归区间预测

区间预测 | Matlab实现CNN-KDE卷积神经网络结合核密度估计多置信区间多变量回归区间预测 目录 区间预测 | Matlab实现CNN-KDE卷积神经网络结合核密度估计多置信区间多变量回归区间预测效果一览基本介绍程序设计参考资料 效果一览 基本介绍 1.Matlab实现CNN-KDE卷积神经网络结合…...

Java集合框架全景解读:从源码到实践精通指南

1. Java集合框架简介 在Java中,集合框架是用于存储和处理数据集合的一组类和接口。它提供了一系列的数据结构,比如列表(List)、集(Set)和映射(Map)。这些数据结构为开发者处理数据提…...

Python | Leetcode Python题解之第107题二叉树的层序遍历II

题目: 题解: class Solution:def levelOrderBottom(self, root: TreeNode) -> List[List[int]]:levelOrder list()if not root:return levelOrderq collections.deque([root])while q:level list()size len(q)for _ in range(size):node q.popl…...

H4vdo 台湾APT-27视频投放工具

地址:https://github.com/MartinxMax/H4vdo 视频 关于 H4vdo RTMP lock 屏播放视频工具,可以向目标发送有效载荷,播放目标的屏幕内容。目标无法曹作计算机 使用方法 安装依赖 根据你的操作系统选择一个安装程序 RTMP 服务端 ./rtsp-simple-server.…...

数据结构(树)

1.树的概念和结构 树,顾名思义,它看起来像一棵树,是由n个结点组成的非线性的数据结构。 下面就是一颗树: 树的一些基本概念: 结点的度:一个结点含有的子树的个数称为该结点的度; 如上图&#…...

HTML静态网页成品作业(HTML+CSS)——川西旅游介绍网页(2个页面)

🎉不定期分享源码,关注不丢失哦 文章目录 一、作品介绍二、作品演示三、代码目录四、网站代码HTML部分代码 五、源码获取 一、作品介绍 🏷️本套采用HTMLCSS,未使用Javacsript代码,共有2个页面。 二、作品演示 三、代…...

MySQL数据库单表查询中查询条件的写法

1.使用比较运算符作为查询条件 ; !; >; >; <; <; 如上图所示&#xff0c;可以使用命令select 字段&#xff0c;字段 from 表名 where Gender “M”; 即挑选出Gender “M” 的教师&#xff0c; 如上图所示&#xff0c;可以使用命令select 字段&#xff0c;…...

SQL靶场搭建

概述 简单介绍一下SQL靶场的搭建&#xff0c;以及在搭建过程中遇到的一些问题。使用该软件搭建靶场相对简单&#xff0c;适合新手小白。当然&#xff0c;也可以在自己的虚拟机下进行搭建&#xff0c;相对来说就较为复杂。本章主要讲解使用Phpstudy进行SQL靶场搭建。 这里我推…...

Cocos Creator 帧动画播放组件制作详解

前言 Cocos Creator 是一个强大的游戏开发工具&#xff0c;提供了丰富的功能和组件&#xff0c;其中帧动画播放组件是游戏开发中常用的组件之一&#xff0c;通过帧动画播放组件可以实现角色动画、特效动画等效果。本文将详细介绍如何使用 Cocos Creator 制作帧动画播放组件&am…...

基于STM32控制的双轮自平衡小车的设计

基于STM32控制的双轮自平衡小车的设计是一项涉及电子、控制理论、机械设计和编程的综合工程。以下是关于该设计的一个概述&#xff0c;包括关键组件、控制策略和示例代码。 设计概述 1. 项目背景 自平衡小车作为一种智能控制系统&#xff0c;其设计和实现涉及到多个学科领域…...

Dijkstra算法在《庆余年》中的应用:范闲的皇宫之旅

❤️❤️❤️ 欢迎来到我的博客。希望您能在这里找到既有价值又有趣的内容&#xff0c;和我一起探索、学习和成长。欢迎评论区畅所欲言、享受知识的乐趣&#xff01; 推荐&#xff1a;数据分析螺丝钉的首页 格物致知 终身学习 期待您的关注 导航&#xff1a; LeetCode解锁100…...

HTML静态网页成品作业(HTML+CSS)——利物浦足球俱乐部介绍网页设计制作(5个页面)

&#x1f389;不定期分享源码&#xff0c;关注不丢失哦 文章目录 一、作品介绍二、作品演示三、代码目录四、网站代码HTML部分代码 五、源码获取 一、作品介绍 &#x1f3f7;️本套采用HTMLCSS&#xff0c;共有5个页面。 二、作品演示 三、代码目录 四、网站代码 HTML部分代…...

mac 查看占用80端口的命令

在 Mac 上&#xff0c;如果你想查看哪个进程正在使用 80 端口&#xff0c;你可以使用 lsof 命令。这个命令非常强大&#xff0c;用于列出被进程打开或使用的文件信息。 打开你的终端&#xff0c;并输入以下命令&#xff1a; sudo lsof -i :80这里&#xff0c;-i :80 选项告诉…...

【Qt常用控件】—— 布局管理器

目录 前言 &#xff08;一&#xff09;垂直布局 &#xff08;二&#xff09;水平布局 &#xff08;三&#xff09;网格布局 &#xff08;四&#xff09;表单布局 &#xff08;五&#xff09;分组布局 &#xff08;六&#xff09;Spacer 总结 前言 之前使⽤Qt在界⾯上…...

模板中的右值引用(万能引用)、引用折叠与完美转发

模板中的右值引用&#xff08;万能引用&#xff09;、引用折叠与完美转发 文章目录 模板中的右值引用&#xff08;万能引用&#xff09;、引用折叠与完美转发一、万能引用与引用折叠1. 模板中的右值引用2. 自动类型推导(auto)与万能引用3. 引用折叠与万能引用4. lambda表达式捕…...

SDMatte惊艳抠图效果展示:10组高难度玻璃/纱布/叶片实测对比图

SDMatte惊艳抠图效果展示&#xff1a;10组高难度玻璃/纱布/叶片实测对比图 1. 开篇&#xff1a;当AI遇见高难度抠图 在图像处理领域&#xff0c;抠图一直是个技术活。特别是遇到玻璃杯、薄纱窗帘、树叶这些半透明或边缘复杂的物体时&#xff0c;传统工具往往力不从心。今天我…...

vLLM-v0.17.1实战案例:为AI编程助手提供毫秒级代码补全服务

vLLM-v0.17.1实战案例&#xff1a;为AI编程助手提供毫秒级代码补全服务 1. vLLM框架简介 vLLM是一个专为大型语言模型(LLM)设计的高性能推理和服务库&#xff0c;其核心目标是提供极致的推理速度和易用性。这个项目最初由加州大学伯克利分校的天空计算实验室开发&#xff0c;…...

RK3128安卓5.1系统APK签名全流程:从signapk.jar到platform.pk8的保姆级教程

RK3128安卓5.1系统APK签名实战指南&#xff1a;工具获取与问题排查全解析 在嵌入式Android开发领域&#xff0c;RK3128芯片因其性价比优势被广泛应用于各类智能终端设备。当开发者需要为这类设备定制系统应用或预装APK时&#xff0c;掌握正确的签名方法至关重要。不同于普通And…...

如何快速使用iOS App Signer:iOS应用签名完整指南

如何快速使用iOS App Signer&#xff1a;iOS应用签名完整指南 【免费下载链接】ios-app-signer DanTheMan827/ios-app-signer: 是一个 iOS 应用的签名工具&#xff0c;适合用于 iOS 开发中&#xff0c;帮助开发者签署和发布他们的 APP。 项目地址: https://gitcode.com/gh_mi…...

OpenClaw多模型切换指南:Qwen3-32B与本地Llama混合调用

OpenClaw多模型切换指南&#xff1a;Qwen3-32B与本地Llama混合调用 1. 为什么需要多模型切换&#xff1f; 去年冬天&#xff0c;当我第一次尝试用OpenClaw自动处理周报时&#xff0c;发现一个有趣的现象&#xff1a;用同一个模型处理文本润色和代码生成任务&#xff0c;效果差…...

GNU Parallel进阶指南:解决管道传参的5个常见坑

GNU Parallel进阶指南&#xff1a;解决管道传参的5个常见坑 在数据处理和批量任务处理领域&#xff0c;GNU Parallel堪称瑞士军刀般的存在。这个看似简单的命令行工具&#xff0c;却能让你的工作效率提升数倍。但就像任何强大的工具一样&#xff0c;掌握其精髓需要跨越一些技术…...

基于comsol的三相电力变压器电磁场与电路耦合计算的电压电流及磁通密度分布分析

comsol三相电力变压器电磁场和电路耦合计算&#xff0c;可以得到变压器高低压绕组电压电流分布以及变压器磁通密度分布三相电力变压器建模这事儿&#xff0c;说难不难说简单也不简单。前两天用COMSOL折腾了个带电路耦合的模型&#xff0c;顺手把绕组电流分布和铁芯磁通都摸清楚…...

C#异步编程完全指南:async/await背后的状态机原理

# C#异步编程完全指南&#xff1a;async/await背后的状态机原理## 引言在现代软件开发中&#xff0c;异步编程已成为构建高响应、高吞吐量应用程序的基石。C# 作为一门不断演进的现代编程语言&#xff0c;从 .NET Framework 4.5 开始引入了 async 和 await 关键字&#xff0c;彻…...

类型注解写错=线上Bug潜伏!:3个导致Pydantic崩溃、FastAPI 500、mypy静默失效的致命细节

第一章&#xff1a;类型注解写错线上Bug潜伏&#xff01;&#xff1a;3个导致Pydantic崩溃、FastAPI 500、mypy静默失效的致命细节泛型未参数化&#xff1a;List 而非 List[str] 的隐式陷阱 Pydantic v2 强制要求泛型类型必须显式参数化。若仅写 List&#xff08;而非 List[str…...

TVM终极模型剪枝指南:如何快速实现结构化与非结构化剪枝

TVM终极模型剪枝指南&#xff1a;如何快速实现结构化与非结构化剪枝 想要让深度学习模型跑得更快、占用更少内存&#xff1f;TVM的模型剪枝功能就是你的最佳选择&#xff01;&#x1f680; 本文为你带来TVM剪枝的完整指南&#xff0c;从基础概念到实际应用&#xff0c;让你快速…...