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

基于服务器使用 apt 安装、配置 Nginx

&#x1f9fe; 一、查看可安装的 Nginx 版本 首先&#xff0c;你可以运行以下命令查看可用版本&#xff1a; apt-cache madison nginx-core输出示例&#xff1a; nginx-core | 1.18.0-6ubuntu14.6 | http://archive.ubuntu.com/ubuntu focal-updates/main amd64 Packages ng…...

css的定位(position)详解:相对定位 绝对定位 固定定位

在 CSS 中&#xff0c;元素的定位通过 position 属性控制&#xff0c;共有 5 种定位模式&#xff1a;static&#xff08;静态定位&#xff09;、relative&#xff08;相对定位&#xff09;、absolute&#xff08;绝对定位&#xff09;、fixed&#xff08;固定定位&#xff09;和…...

学习STC51单片机32(芯片为STC89C52RCRC)OLED显示屏2

每日一言 今天的每一份坚持&#xff0c;都是在为未来积攒底气。 案例&#xff1a;OLED显示一个A 这边观察到一个点&#xff0c;怎么雪花了就是都是乱七八糟的占满了屏幕。。 解释 &#xff1a; 如果代码里信号切换太快&#xff08;比如 SDA 刚变&#xff0c;SCL 立刻变&#…...

苹果AI眼镜:从“工具”到“社交姿态”的范式革命——重新定义AI交互入口的未来机会

在2025年的AI硬件浪潮中,苹果AI眼镜(Apple Glasses)正在引发一场关于“人机交互形态”的深度思考。它并非简单地替代AirPods或Apple Watch,而是开辟了一个全新的、日常可接受的AI入口。其核心价值不在于功能的堆叠,而在于如何通过形态设计打破社交壁垒,成为用户“全天佩戴…...

日常一水C

多态 言简意赅&#xff1a;就是一个对象面对同一事件时做出的不同反应 而之前的继承中说过&#xff0c;当子类和父类的函数名相同时&#xff0c;会隐藏父类的同名函数转而调用子类的同名函数&#xff0c;如果要调用父类的同名函数&#xff0c;那么就需要对父类进行引用&#…...

安卓基础(Java 和 Gradle 版本)

1. 设置项目的 JDK 版本 方法1&#xff1a;通过 Project Structure File → Project Structure... (或按 CtrlAltShiftS) 左侧选择 SDK Location 在 Gradle Settings 部分&#xff0c;设置 Gradle JDK 方法2&#xff1a;通过 Settings File → Settings... (或 CtrlAltS)…...

GraphQL 实战篇:Apollo Client 配置与缓存

GraphQL 实战篇&#xff1a;Apollo Client 配置与缓存 上一篇&#xff1a;GraphQL 入门篇&#xff1a;基础查询语法 依旧和上一篇的笔记一样&#xff0c;主实操&#xff0c;没啥过多的细节讲解&#xff0c;代码具体在&#xff1a; https://github.com/GoldenaArcher/graphql…...

DiscuzX3.5发帖json api

参考文章&#xff1a;PHP实现独立Discuz站外发帖(直连操作数据库)_discuz 发帖api-CSDN博客 简单改造了一下&#xff0c;适配我自己的需求 有一个站点存在多个采集站&#xff0c;我想通过主站拿标题&#xff0c;采集站拿内容 使用到的sql如下 CREATE TABLE pre_forum_post_…...

在 Visual Studio Code 中使用驭码 CodeRider 提升开发效率:以冒泡排序为例

目录 前言1 插件安装与配置1.1 安装驭码 CodeRider1.2 初始配置建议 2 示例代码&#xff1a;冒泡排序3 驭码 CodeRider 功能详解3.1 功能概览3.2 代码解释功能3.3 自动注释生成3.4 逻辑修改功能3.5 单元测试自动生成3.6 代码优化建议 4 驭码的实际应用建议5 常见问题与解决建议…...

高效的后台管理系统——可进行二次开发

随着互联网技术的迅猛发展&#xff0c;企业的数字化管理变得愈加重要。后台管理系统作为数据存储与业务管理的核心&#xff0c;成为了现代企业不可或缺的一部分。今天我们要介绍的是一款名为 若依后台管理框架 的系统&#xff0c;它不仅支持跨平台应用&#xff0c;还能提供丰富…...