数据结构——图的基础知识与其表示
一:图的定义
由顶点的集合和边的集合组成;常以 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…...
JavaSec-RCE
简介 RCE(Remote Code Execution),可以分为:命令注入(Command Injection)、代码注入(Code Injection) 代码注入 1.漏洞场景:Groovy代码注入 Groovy是一种基于JVM的动态语言,语法简洁,支持闭包、动态类型和Java互操作性,…...
Linux相关概念和易错知识点(42)(TCP的连接管理、可靠性、面临复杂网络的处理)
目录 1.TCP的连接管理机制(1)三次握手①握手过程②对握手过程的理解 (2)四次挥手(3)握手和挥手的触发(4)状态切换①挥手过程中状态的切换②握手过程中状态的切换 2.TCP的可靠性&…...
(转)什么是DockerCompose?它有什么作用?
一、什么是DockerCompose? DockerCompose可以基于Compose文件帮我们快速的部署分布式应用,而无需手动一个个创建和运行容器。 Compose文件是一个文本文件,通过指令定义集群中的每个容器如何运行。 DockerCompose就是把DockerFile转换成指令去运行。 …...
tree 树组件大数据卡顿问题优化
问题背景 项目中有用到树组件用来做文件目录,但是由于这个树组件的节点越来越多,导致页面在滚动这个树组件的时候浏览器就很容易卡死。这种问题基本上都是因为dom节点太多,导致的浏览器卡顿,这里很明显就需要用到虚拟列表的技术&…...
微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据
微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据 Power Query 具有大量专门帮助您清理和准备数据以供分析的功能。 您将了解如何简化复杂模型、更改数据类型、重命名对象和透视数据。 您还将了解如何分析列,以便知晓哪些列包含有价值的数据,…...
基于 TAPD 进行项目管理
起因 自己写了个小工具,仓库用的Github。之前在用markdown进行需求管理,现在随着功能的增加,感觉有点难以管理了,所以用TAPD这个工具进行需求、Bug管理。 操作流程 注册 TAPD,需要提供一个企业名新建一个项目&#…...
代码随想录刷题day30
1、零钱兑换II 给你一个整数数组 coins 表示不同面额的硬币,另给一个整数 amount 表示总金额。 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额,返回 0 。 假设每一种面额的硬币有无限个。 题目数据保证结果符合 32 位带…...
给网站添加live2d看板娘
给网站添加live2d看板娘 参考文献: stevenjoezhang/live2d-widget: 把萌萌哒的看板娘抱回家 (ノ≧∇≦)ノ | Live2D widget for web platformEikanya/Live2d-model: Live2d model collectionzenghongtu/live2d-model-assets 前言 网站环境如下,文章也主…...
6个月Python学习计划 Day 16 - 面向对象编程(OOP)基础
第三周 Day 3 🎯 今日目标 理解类(class)和对象(object)的关系学会定义类的属性、方法和构造函数(init)掌握对象的创建与使用初识封装、继承和多态的基本概念(预告) &a…...
深入浅出WebGL:在浏览器中解锁3D世界的魔法钥匙
WebGL:在浏览器中解锁3D世界的魔法钥匙 引言:网页的边界正在消失 在数字化浪潮的推动下,网页早已不再是静态信息的展示窗口。如今,我们可以在浏览器中体验逼真的3D游戏、交互式数据可视化、虚拟实验室,甚至沉浸式的V…...
