数据结构——图的基础知识与其表示
一:图的定义
由顶点的集合和边的集合组成;常以 G(V,E) 表示,G 代表图,V代表 顶点的集合,E代表边的集合;
如图:
在G1图中,有 0~4 五个顶点,有 0-1,0-2,0-4,1-2,2-3,3-4 六条边 ;

二:图的
目录
一:图的定义
二:图的
分类
(1)有/无向图
(2 带/不带权图
三:图的表示
1. 邻接矩阵
1.1 不带权的邻接矩阵:
1.2 带权的邻阶矩阵:
四:实际应用
1.稀疏图
2.稠密图
3.特殊情况
分类
(1)有/无向图
我们根据 边是否有方向分为 有向图,无向图;
如图,无向图中,0可以到1,1也可以到0,0和1之间是等价的;
无向图中,0可以到1,但是1不可以到0;
(2 带/不带权图
我们根据边是否有权重分为带权图,不带权图;
边的度量可以表示时间,距离等具体的量(如G3);
当然,边与边之间的度量可以是不同的(如G4);

三:图的表示
1. 邻接矩阵
即使用二维数据来表示图。
1.1 不带权的邻接矩阵:
1代表两顶点连通,0代表不连通。某顶点带自身的边一般用0表示,

不过,也可以根据需要用 1 表示;

1.2 带权的邻阶矩阵:
顶点之间不连通常用 +∞ 来表示,顶点到自身的边一般标记为 0 ;

2.邻接表
使用顺序和链式相结合的方式存储图,指针的连接代表相连,与有向还是无向,带权还是不带权无关

如果需要表示权值的话,我们可以在节点中增加额外的数据域进行存储,

四:实际应用
实际应用时,我们通常根据结点和边的个数来选择邻接矩阵或邻接表来表示图
1.稀疏图
边的条数远远小于顶点的个数:E<<V的平方,选择邻接表,毕竟添加元素方便;
2.稠密图
边的条数远远接近顶点的个数:E 接近 V的平方,选择邻接矩阵;
3.特殊情况
比如我们要判断两个顶点之间是否连通,需要采用邻接矩阵来表示图,因为二维数组遍历的时间复杂度为O(1),这会提高找寻的效率;
相关文章:
数据结构——图的基础知识与其表示
一:图的定义 由顶点的集合和边的集合组成;常以 G(V,E) 表示,G 代表图,V代表 顶点的集合,E代表边的集合; 如图: 在G1图中,有 0~4 五个顶点,有 0-1,0-2&…...
数据库管理-第187期 23ai:怎么用SQL创建图(20240510)
数据库管理187期 2024-05-10 数据库管理-第187期 23ai:怎么用SQL创建图(20240510)1 安装PGX1.1 数据库配置对应用户1.2 使用RPM包安装Graph Server1.3 安装Oracle Graph Client1.4 访问PGX页面 2 SQL Property Graph2.1 创建SQL属性图2.2 关于点和边图元…...
基于VOLOPV2的自动驾驶环境感知系统
基于VOLOPV2的自动驾驶环境感知系统是一个复杂的系统,它主要负责实时检测并识别周围环境中的各种物体和信息,为自动驾驶车辆提供必要的感知数据。以下是对该系统的一个简要介绍: 环境感知是自动驾驶系统中的一个关键部分,它依赖于…...
使用Python爬虫会遇到的问题和解决方法(包含案例)
一、HTTP错误(如403 Forbidden) 问题描述: 当使用requests库发起请求时,可能会遇到HTTP 403 Forbidden错误,这通常意味着服务器理解了请求,但是拒绝执行它。 解决方法: 1.设置headers…...
Spring Boot 读取配置优先级顺序是什么?
在使用 Spring Boot 进行开发时,配置文件是非常重要的一部分,它可以用来配置应用程序的行为、数据源、日志级别等信息。 但是,当配置文件中存在多个配置来源时,Spring Boot 是如何确定读取配置的优先级顺序的呢? 本文…...
数据挖掘(二)数据预处理
前言 基于国防科技大学 丁兆云老师的《数据挖掘》 数据挖掘 数据挖掘(一)数据类型与统计 2、数据预处理 2.1数据清理 缺失值处理: from sklearn.impute import SimpleImputer# 创建一个SimpleImputer对象,指定缺失值的处理策略…...
docker学习-docker常用其他命令整理
随便写写,后面有空再更新 镜像命令,容器命令已在之前略有更新,这次不写, 一、后台启动命令 # 命令 docker run -d 容器名 # 例子 docker run -d centos # 启动centos,使用后台方式启动 # 问题: 使用doc…...
【matlab基础知识代码】(十六)代数方程的图解法多项式型方程的准解析解方法
>> ezplot(exp(-3*t)*sin(4*t2)4*exp(-0.5*t)*cos(2*t)-0.5,[0 5]), line([0 5],[0 0]) 验证 >> t0.6738; >> exp(-3*t)*sin(4*t2)4*exp(-0.5*t)*cos(2*t)-0.5 ans -2.9852e-04 >> ezplot(x^2*exp(-x*y^2/2)exp(-x/2)*sin(x*y)) >> hold on; …...
智能奶柜:健康生活新风尚
智能奶柜:健康生活新风尚 在快节奏的都市生活中,健康与便利成为了现代人的双重追求。而在这两者交汇之处,智能奶柜应运而生,它不仅是科技与生活的完美融合,更是日常营养补给的智慧之选。 清晨的第一缕温暖 —— 新鲜…...
SpringBoot 集成 FFmpeg 解析音视频
文章目录 1 摘要2 核心 Maven 依赖3 核心代码3.1 FFmpeg 解析音视频工具类3.2 音视频文件信息参数3.3 音视频文件上传Controller3.4 application 配置文件 4 测试数据4.1 视频文件解析4.2 音频文件解析 5 注意事项5.1 文件必须在本地 6 推荐参考文档7 Github 源码 1 摘要 FFmp…...
基于单片机的直流电机测速装置研究与设计
摘要: 基于单片机的直流电机测速装置采用了对直流电机的中枢供电回路串联取样电阻的方式实现对电机转速的精确实时测量。系统由滤波电路、信号放大电路、单片机控制电路以及稳压电源等功能模块电路构成。工作过程中高频磁环作为载体,利用电磁感应的基本原理对直流电…...
【快捷部署】022_ZooKeeper(3.5.8)
📣【快捷部署系列】022期信息 编号选型版本操作系统部署形式部署模式复检时间022ZooKeeper3.5.8Ubuntu 20.04tar包单机2024-05-07 一、快捷部署 #!/bin/bash ################################################################################# # 作者ÿ…...
引领AI数据标注新纪元:景联文科技为智能未来筑基
在人工智能蓬勃发展的今天,数据如同燃料,驱动着每一次技术飞跃。在这场智能革命的浪潮中,景联文科技凭借其深厚的专业实力与前瞻性的战略眼光,正站在行业前沿,为全球的人工智能企业提供坚实的数据支撑。 全国布局&…...
多模态大语言模型和 Apple 的 MM1
原文地址:multimodal-large-language-models-apples-mm1 2024 年 4 月 13 日 抽象是计算机科学中最关键的概念之一,具有一些最强大的影响。从简单的角度来看,抽象就是将某一事物应用于多种不同情况的能力。例如,如果你创造了一种…...
算法day04
第一题 : 209. 长度最小的子数组 有上题可知,我们会采用双指针和单调性的思路来解决 我们本题采用左右双指针从数组的0位置同向前进,所以将此类模型称为滑块; 步骤思路如下: 步骤一: 定义所有双指针都指向…...
电信网关配置管理系统 rewrite.php 文件上传致RCE漏洞复现
0x01 产品简介 中国电信集团有限公司(英文名称“China Telecom”、简称“中国电信”)成立于2000年9月,是中国特大型国有通信企业、上海世博会全球合作伙伴。电信网关配置管理系统是一个用于管理和配置电信网络中网关设备的软件系统。它可以帮助网络管理员实现对网关设备的远…...
从零学算法14
14. 最长公共前缀 编写一个函数来查找字符串数组中的最长公共前缀。 如果不存在公共前缀,返回空字符串 “”。 示例 1: 输入:strs [“flower”,“flow”,“flight”] 输出:“fl” 示例 2: 输入:strs [“d…...
[入门] Unity Shader前置知识(5) —— 向量的运算
在Unity中,向量无处不在,我想很多人都使用过向量类的内置方法 normalized() 吧,我们都知道该方法是将其向量归一化从而作为一个方向与速度相乘,以达到角色朝任一方向移动时速度都相等的效果,但内部具体是如何将该向量进…...
html的i标签 “\e905“ font-family 字体没有效果
一、html的i标签 “\e905” 没有效果 在HTML和CSS中,\e905 这样的字符通常与字体图标(Font Icons)或自定义字体(Custom Fonts)中的Unicode字符相关。具体来说,\e905 是一个Unicode转义序列,但它…...
Golang reflect.MakeFunc() 的用法及示例
Golang 作为一门强类型语言,在某些场景下,我们需要动态地创建函数或者修改函数,这个时候就可以使用反射的方法去实现。在反射中,我们可以使用 reflect.MakeFunc() 方法来创建一个新的函数,本文我将介绍使用反射及其 Ma…...
Ascend NPU上适配Step-Audio模型
1 概述 1.1 简述 Step-Audio 是业界首个集语音理解与生成控制一体化的产品级开源实时语音对话系统,支持多语言对话(如 中文,英文,日语),语音情感(如 开心,悲伤)&#x…...
JVM暂停(Stop-The-World,STW)的原因分类及对应排查方案
JVM暂停(Stop-The-World,STW)的完整原因分类及对应排查方案,结合JVM运行机制和常见故障场景整理而成: 一、GC相关暂停 1. 安全点(Safepoint)阻塞 现象:JVM暂停但无GC日志,日志显示No GCs detected。原因:JVM等待所有线程进入安全点(如…...
【7色560页】职场可视化逻辑图高级数据分析PPT模版
7种色调职场工作汇报PPT,橙蓝、黑红、红蓝、蓝橙灰、浅蓝、浅绿、深蓝七种色调模版 【7色560页】职场可视化逻辑图高级数据分析PPT模版:职场可视化逻辑图分析PPT模版https://pan.quark.cn/s/78aeabbd92d1...
Java求职者面试指南:Spring、Spring Boot、MyBatis框架与计算机基础问题解析
Java求职者面试指南:Spring、Spring Boot、MyBatis框架与计算机基础问题解析 一、第一轮提问(基础概念问题) 1. 请解释Spring框架的核心容器是什么?它在Spring中起到什么作用? Spring框架的核心容器是IoC容器&#…...
GitFlow 工作模式(详解)
今天再学项目的过程中遇到使用gitflow模式管理代码,因此进行学习并且发布关于gitflow的一些思考 Git与GitFlow模式 我们在写代码的时候通常会进行网上保存,无论是github还是gittee,都是一种基于git去保存代码的形式,这样保存代码…...
【JavaSE】多线程基础学习笔记
多线程基础 -线程相关概念 程序(Program) 是为完成特定任务、用某种语言编写的一组指令的集合简单的说:就是我们写的代码 进程 进程是指运行中的程序,比如我们使用QQ,就启动了一个进程,操作系统就会为该进程分配内存…...
C语言中提供的第三方库之哈希表实现
一. 简介 前面一篇文章简单学习了C语言中第三方库(uthash库)提供对哈希表的操作,文章如下: C语言中提供的第三方库uthash常用接口-CSDN博客 本文简单学习一下第三方库 uthash库对哈希表的操作。 二. uthash库哈希表操作示例 u…...
Vue 模板语句的数据来源
🧩 Vue 模板语句的数据来源:全方位解析 Vue 模板(<template> 部分)中的表达式、指令绑定(如 v-bind, v-on)和插值({{ }})都在一个特定的作用域内求值。这个作用域由当前 组件…...
DiscuzX3.5发帖json api
参考文章:PHP实现独立Discuz站外发帖(直连操作数据库)_discuz 发帖api-CSDN博客 简单改造了一下,适配我自己的需求 有一个站点存在多个采集站,我想通过主站拿标题,采集站拿内容 使用到的sql如下 CREATE TABLE pre_forum_post_…...
企业大模型服务合规指南:深度解析备案与登记制度
伴随AI技术的爆炸式发展,尤其是大模型(LLM)在各行各业的深度应用和整合,企业利用AI技术提升效率、创新服务的步伐不断加快。无论是像DeepSeek这样的前沿技术提供者,还是积极拥抱AI转型的传统企业,在面向公众…...
