当前位置: 首页 > 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表达式捕…...

如何快速搭建QQ机器人?LuckyLilliaBot入门指南

如何快速搭建QQ机器人&#xff1f;LuckyLilliaBot入门指南 【免费下载链接】LuckyLilliaBot NTQQ的OneBot API插件 项目地址: https://gitcode.com/gh_mirrors/li/LuckyLilliaBot 在数字化时代&#xff0c;QQ机器人开发已成为自动化交互的重要工具。LuckyLilliaBot作为N…...

MindSpore mint 模块学习

1. 模块概述mindspore.mint是 MindSpore 框架提供的一个功能接口子模块&#xff0c;旨在提供大量与业界主流深度学习框架&#xff08;如 PyTorch&#xff09;保持一致的 functional、nn、优化器等 API。使熟悉主流框架的用户能够快速上手。性能特点&#xff1a;在图编译模式为 …...

1949–2024年中国县级行政区划(逐年)|全国范围、75年连续、SHP格式

&#x1f50d; 数据简介 本数据集完整覆盖 1949年至2024年 共 76个年份 的中国县级行政区划边界&#xff0c;是目前公开可获取的时间跨度最长、更新粒度最细的全国县级历史区划产品。 每一年份均提供独立、闭合、无重叠的面状矢量边界&#xff0c;属性表包含标准名称、行政区划…...

Papercups开源客户聊天系统:7步快速定制部署完整指南

Papercups开源客户聊天系统&#xff1a;7步快速定制部署完整指南 【免费下载链接】papercups Open-source live customer chat 项目地址: https://gitcode.com/gh_mirrors/pa/papercups Papercups是一个功能强大的开源实时客户聊天系统&#xff0c;专为注重数据隐私和安…...

N诺机试题

2.整除&#xff08;末尾无空格用printf“ ”&#xff09;#include<stdio.h>int main(){int count0;for(int i100;i<1000;i){if(i%50&&i%60){printf("%d",i);count;if(count%100) printf("\n");else printf(" "); }}return 0;…...

终极指南:使用compressorjs实现专业级前端图片压缩与编辑功能

终极指南&#xff1a;使用compressorjs实现专业级前端图片压缩与编辑功能 【免费下载链接】compressorjs compressorjs: 是一个JavaScript图像压缩库&#xff0c;使用浏览器原生的canvas.toBlob API进行图像压缩。 项目地址: https://gitcode.com/gh_mirrors/co/compressorjs…...

美团、腾讯、字节怎么选?3个真实案例告诉你答案

美团、腾讯、字节怎么选&#xff1f;3个真实案例告诉你答案 2026校招季&#xff0c;三个朋友的不同选择 大厂直通车-校招大礼包&#xff1a;入口入口 写在前面 2026届秋招结束了。 我的三个朋友小A、小B、小C都拿到了心仪的offer。有意思的是&#xff0c;他们分别选了字节、腾…...

HUNYUAN-MT企业级Java集成指南:构建高并发翻译微服务

HUNYUAN-MT企业级Java集成指南&#xff1a;构建高并发翻译微服务 1. 引言 想象一下&#xff0c;你负责的电商平台刚刚接到一个来自海外的百万级订单&#xff0c;但商品详情、用户手册全是中文。市场团队急等着把上万页的产品资料翻译成十几种语言&#xff0c;时间窗口只有短短…...

Comsol热流耦合拓扑优化:最大化放热量与功率耗散的探索

Comsol热流耦合拓扑优化。 目标函数采用最大化放热量和功率耗散。在工程领域&#xff0c;热流耦合问题一直是研究的重点&#xff0c;尤其是如何通过拓扑优化来实现特定目标&#xff0c;比如最大化放热量和功率耗散&#xff0c;这对于提高系统性能至关重要。而Comsol作为一款强大…...

Claude Code 速查表

其中的&#xff1a;键盘快捷键常规控制Ctrl C&#xff1a;取消输入 / 生成Ctrl D&#xff1a;退出会话Ctrl L&#xff1a;清屏Ctrl O&#xff1a;切换详细输出Ctrl R&#xff1a;反向搜索历史Ctrl G&#xff1a;在编辑器中打开提示Ctrl B&#xff1a;后台运行任务Ctrl …...