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

数据结构-图的基本概念

图的定义

        图时由非空的顶点集合和一个描述顶点之间关系的集合组成。可以定义为:

                                        ​​​​​​​        ​​​​​​​        ​​​​​​​        G=(V,E)

         G表示一个图,V表示点集,E表示边集。集合E的每一个二元组都包含两个值v_{i}v_{j},表示为一条边的两个顶点。

图的相关术语

        (1)无向图

        在一个图中顶点之间的连线没有指定方向。

        (2)有向图

        在一个图中顶点之间的连线有指定方向

        (3)顶点、边

        在无向图中,两个顶点之间的连线称为边,边用顶点的无序偶对(v,w)表示,称顶点v和顶点w互为邻接点。

        (4)弧、弧头、弧尾

        在有向图中,两个顶点之间的连线称为弧,弧用顶点的有序偶对<v_{i},v_{j}>表示,有序偶对的第一个结点v_{i}称为弧尾(图中没有箭头的一端),第二个结点v_{j}称为弧头(图中有结点的一端)。若<v,w>是一条弧,则称顶点v邻接到w

        (5)无向完全图

        在一个无向图中,如果任意两点都有一条直接边相连接,则称为无向完全图。

        在一个n个顶点的无向完全图中有n(n-1)/2条边。

        (6)有向完全图

        在一个有向图中,如果任意两点都有方向互为相反的两条弧相连接,则称为有向完全图。

        在一个n个顶点的有向完全图中有n(n-1)条边。

        (7)稠密图、稀疏图

        若一个图接近完全图,称为稠密图

        边数很少的图(e<<n(n-1))为稀疏图

        (8)度

        顶点的度是与顶点相连接的边数,记为D(v)

        在有向图中有入度和出度的区分。

        入度指的是以顶点v为终点的弧的数目,记为ID(v)

        出度指的是以顶点v为起点的弧的数目,记为OD(v)

        对于具有n个顶点、e条边的图,顶点v_{i}的度D(v_{i})与顶点的个数以及边的数目的关系为:

        ​​​​​​​        ​​​​​​​        ​​​​​​​        ​​​​​​​        ​​​​​​​        ​​​​​​​        e=\frac{1}{2}\sum_{i=1}^{n}D(v_{i})

         (9)边权、网图

        当图的边带有数值信息时,这种数值称为权。

        每条边或弧都带权的图称为带权图或网。

        (10)路径、路径长度

        在无向图中,顶点v_{p}到顶点v_{q}之间的路径指序列v_{p},v_{i1},v_{i2}...v_{q},路径上边的数目称为路径长度。有向图中路径也是有向的。

        (11)回路,简单回路

        起点和终点相同的路径称为回路或环。除了第一个顶点与最后一个顶点之外其他顶点不重复出现的回路称为简单回路。

        (12)连通图

        在无向图中,任意两个顶点都相互连通,称为连通图。

        (13)强连通图

        在有向图中,如果从一个顶点v_{i}到另一个顶点v_{j}均有一条有向路径,则该图为强连通图

相关文章:

数据结构-图的基本概念

图的定义 图时由非空的顶点集合和一个描述顶点之间关系的集合组成。可以定义为&#xff1a; ​​​​​​​ ​​​​​​​ ​​​​​​​ G表示一个图&#xff0c;V表示点集&#xff0c;E表示边集。集合E的每一个二元组都包含两个值和&#xff0c;表示…...

【HarmonyOS NEXT 】鸿蒙generateBarcode (码图生成)

本模块支持将字符串转换为二维码或条形码&#xff0c;目前已支持的码制式为EAN-8、EAN-13、UPC-A、UPC-E、Codabar、Code 39、Code 93、Code 128、ITF-14、QR Code、Data Matrix、PDF417、Aztec。暂时不支持多功能码生成。 起始版本&#xff1a;4.1.0(11) 导入模块 import {…...

python测试工程师 之 unittest框架总结

unittest 学习目标unittest 框架的基本使⽤⽅法(组成)断⾔的使⽤ (让程序⾃动的判断预期结果和实际结果是否相符)参数化(多个测试数据, 测试代码写⼀份 传参)⽣成测试报告 复习pythonunittest 框架的介绍核⼼要素(组成)1. TestCase 测试⽤例, 这个测试⽤例是 unittest 的组成部…...

微服务中的相关概念

Eureka Eureka 是由 Netflix 开发的一个服务发现和注册中心&#xff0c;广泛应用于微服务架构中。Eureka 主要用于管理和协调分布式服务的注册和发现&#xff0c;确保各个服务之间能够方便地找到并通信。它是 Netflix OSS&#xff08;Netflix Open Source Software&#xff09…...

常见的设计模式

设计模式是一套被反复使用的、代码设计经验的总结。它们被用来解决软件开发中的某些常见问题&#xff0c;提高代码的可维护性、可扩展性和重用性。设计模式主要分为三大类&#xff1a;创建型模式、结构型模式和行为型模式。以下是一些常见的设计模式及其简要说明&#xff1a; …...

Camtasia2024中文版最新电脑录屏剪辑神器!

大家好&#xff0c;今天我要安利一个我最近超级喜欢的工具——Camtasia2024中文版&#xff01;这款软件真的太棒了&#xff0c;它让我的视频编辑工作变得更加轻松和高效。如果你也对视频制作感兴趣&#xff0c;那么一定要尝试一下这款神器哦&#xff01; Camtasia2024win-正式…...

【性能优化】表分区实践最佳案例

背景 随着数字化建设的持续深入&#xff0c;企业的业务规模迎来了高速发展&#xff0c;其数据规模也呈现爆炸式增长&#xff0c;如果继续使用传统解决方案&#xff0c;将所有数据存储在一个表中&#xff0c;对数据的查询和维护效率将是一个巨大的挑战&#xff0c;在这个背景下…...

力扣SQL50 项目员工 I ROUND AVG

Problem: 1075. 项目员工 I &#x1f468;‍&#x1f3eb; 参考题解 Code select project_id,ROUND(AVG(e.experience_years),2) as average_years FROMproject as p LEFT JOINemployee as e ONp.employee_id e.employee_id GROUP BYp.project_id;...

nuscenes 数据集学习笔记

目录 数据信息类型: 数据信息类型: Map & Camera(png), Lidar(激光雷达) & Radar(雷达)(pcd), Json 文件结构(以v1.0-mini为例): maps: 存放Map的png文件samples: 存放Camera, Lidar, Radar关键非结构化数据信息, 带标注sweeps: 存放Camera, Lidar, Radar 次要非结构…...

在Windows上用MinGW编译OpenCV项目运行全流程

一、准备软件 OpenCV源码CMake工具MinGW工具链&#xff08;需要选用 posix 线程版本&#xff1a;原因见此&#xff09; 二、操作步骤 官网提供了VC16构建版本的二进制包&#xff0c;但是没有给出GCC编译的版本。所以如果使用MinGW进行构建&#xff0c;那就只能从源码开始构建…...

用Vite基于Vue3+ts+DataV+ECharts开发数据可视化大屏,即能快速开发又能保证屏幕适配

数据可视化大屏 基于 Vue3、Typescript、DataV、ECharts5 框架的大数据可视化&#xff08;大屏展示&#xff09;开发。此项目vue3实现界面&#xff0c;采用新版动态屏幕适配方案&#xff0c;全局渲染组件封装&#xff0c;支持数据动态刷新渲染、内部DataV、ECharts图表都支持自…...

大二学生眼中的Netty?基于Netty实现内网穿透!

爷的开场白 掘金的朋友们大家好&#xff01;我是新来的Java练习生 CodeCodeBond&#xff01; 这段时间呢&#xff0c;博主在学习Netty&#xff0c;想做一个自己感兴趣好玩的东西&#xff0c;那就是内网穿透&#xff01;&#xff01;&#xff08;已经实现主要代理功能但有待优化…...

JavaStringBuffer与StringBuilder

StringBuffer、StringBuilder 文章目录 StringBuffer、StringBuilderStringBuffer和StringBuilder的理解可变性分析对于String对于StringBuilder 常用方法执行效率对比 StringBuffer和StringBuilder的理解 String 不可变的字符序列 StringBuffer 可变的字符序列 JDK1.0声明&…...

云徙科技助力竹叶青实现用户精细化运营,拉动全渠道销售额增长

竹叶青茶以其别具一格的风味与深厚的历史底蕴&#xff0c;一直被誉为茶中瑰宝。历经千年的传承与创新&#xff0c;竹叶青不仅坚守着茶叶品质的极致追求&#xff0c;更在数字化的浪潮中&#xff0c;率先打破传统&#xff0c;以科技力量赋能品牌&#xff0c;成为茶行业的领军者。…...

深度揭秘:深度学习框架下的神经网络架构进化

深度学习框架下的神经网络架构经历了从基础到复杂的显著进化&#xff0c;这一进程不仅推动了人工智能领域的突破性进展&#xff0c;还极大地影响了诸多行业应用。本文旨在深入浅出地揭示这一进化历程&#xff0c;探讨关键架构的创新点及其对现实世界的影响。 引言&#xff1a;…...

MySQL的DML语句

文章目录 ☃️概述☃️DML☃️添加数据☃️更新和删除数据☃️DML的重要性 ☃️概述 MySQL 通用语法分类 ● DDL: 数据定义语言&#xff0c;用来 定义数据库对象&#xff08;数据库、表、字段&#xff09; ● DML: 数据操作语言&#xff0c;用来对数据库表中的数据进行增删改 …...

Wireshark的基本用法以及注意事项

Wireshark 是一个流行的网络协议分析工具&#xff0c;可以捕获和分析网络数据包。以下是一些常见的 Wireshark 的用法&#xff1a; 安装和启动&#xff1a;首先需要下载和安装 Wireshark。安装完成后&#xff0c;可以通过启动 Wireshark 应用程序来打开它。 选择网络接口&…...

集团门户网站的设计

管理员账户功能包括&#xff1a;系统首页&#xff0c;个人中心&#xff0c;管理员管理&#xff0c;论坛管理&#xff0c;集团文化管理&#xff0c;基础数据管理&#xff0c;公告通知管理 前台账户功能包括&#xff1a;系统首页&#xff0c;个人中心&#xff0c;论坛&#xff0…...

Tomcat基础详解

第一篇&#xff1a;Tomcat基础篇 lecture&#xff1a;邓澎波 一、构建Tomcat源码环境 工欲善其事必先利其器&#xff0c;为了学好Tomcat源码&#xff0c;我们需要先在本地构建一个Tomcat的运行环境。 1.源码环境下载 源码有两种下载方式&#xff1a; 1.1 官网下载 https://…...

【Python爬虫】爬取名人名言页面并进行简单的数据清洗(入门级)

目录 资源链接 一、网站选择 二、数据爬取要求 三、数据清洗要求 四、实现代码 1.数据采集 2.数据清洗 资源链接 下面有笔者所放的源码下载链接&#xff0c;读者可自行下载&#xff1a; 链接&#xff1a;https://pan.baidu.com/s/1YmTdlnbSJLvLrrx92zz6Qg 提取码&…...

关于 WASM:1. WASM 基础原理

一、WASM 简介 1.1 WebAssembly 是什么&#xff1f; WebAssembly&#xff08;WASM&#xff09; 是一种能在现代浏览器中高效运行的二进制指令格式&#xff0c;它不是传统的编程语言&#xff0c;而是一种 低级字节码格式&#xff0c;可由高级语言&#xff08;如 C、C、Rust&am…...

排序算法总结(C++)

目录 一、稳定性二、排序算法选择、冒泡、插入排序归并排序随机快速排序堆排序基数排序计数排序 三、总结 一、稳定性 排序算法的稳定性是指&#xff1a;同样大小的样本 **&#xff08;同样大小的数据&#xff09;**在排序之后不会改变原始的相对次序。 稳定性对基础类型对象…...

【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的“no matching...“系列算法协商失败问题

【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的"no matching..."系列算法协商失败问题 摘要&#xff1a; 近期&#xff0c;在使用较新版本的OpenSSH客户端连接老旧SSH服务器时&#xff0c;会遇到 "no matching key exchange method found"​, "n…...

现有的 Redis 分布式锁库(如 Redisson)提供了哪些便利?

现有的 Redis 分布式锁库&#xff08;如 Redisson&#xff09;相比于开发者自己基于 Redis 命令&#xff08;如 SETNX, EXPIRE, DEL&#xff09;手动实现分布式锁&#xff0c;提供了巨大的便利性和健壮性。主要体现在以下几个方面&#xff1a; 原子性保证 (Atomicity)&#xff…...

jmeter聚合报告中参数详解

sample、average、min、max、90%line、95%line,99%line、Error错误率、吞吐量Thoughput、KB/sec每秒传输的数据量 sample&#xff08;样本数&#xff09; 表示测试中发送的请求数量&#xff0c;即测试执行了多少次请求。 单位&#xff0c;以个或者次数表示。 示例&#xff1a;…...

uniapp 小程序 学习(一)

利用Hbuilder 创建项目 运行到内置浏览器看效果 下载微信小程序 安装到Hbuilder 下载地址 &#xff1a;开发者工具默认安装 设置服务端口号 在Hbuilder中设置微信小程序 配置 找到运行设置&#xff0c;将微信开发者工具放入到Hbuilder中&#xff0c; 打开后出现 如下 bug 解…...

QT开发技术【ffmpeg + QAudioOutput】音乐播放器

一、 介绍 使用ffmpeg 4.2.2 在数字化浪潮席卷全球的当下&#xff0c;音视频内容犹如璀璨繁星&#xff0c;点亮了人们的生活与工作。从短视频平台上令人捧腹的搞笑视频&#xff0c;到在线课堂中知识渊博的专家授课&#xff0c;再到影视平台上扣人心弦的高清大片&#xff0c;音…...

AxureRP-Pro-Beta-Setup_114413.exe (6.0.0.2887)

Name&#xff1a;3ddown Serial&#xff1a;FiCGEezgdGoYILo8U/2MFyCWj0jZoJc/sziRRj2/ENvtEq7w1RH97k5MWctqVHA 注册用户名&#xff1a;Axure 序列号&#xff1a;8t3Yk/zu4cX601/seX6wBZgYRVj/lkC2PICCdO4sFKCCLx8mcCnccoylVb40lP...

Java详解LeetCode 热题 100(26):LeetCode 142. 环形链表 II(Linked List Cycle II)详解

文章目录 1. 题目描述1.1 链表节点定义 2. 理解题目2.1 问题可视化2.2 核心挑战 3. 解法一&#xff1a;HashSet 标记访问法3.1 算法思路3.2 Java代码实现3.3 详细执行过程演示3.4 执行结果示例3.5 复杂度分析3.6 优缺点分析 4. 解法二&#xff1a;Floyd 快慢指针法&#xff08;…...

Xcode 16 集成 cocoapods 报错

基于 Xcode 16 新建工程项目&#xff0c;集成 cocoapods 执行 pod init 报错 ### Error RuntimeError - PBXGroup attempted to initialize an object with unknown ISA PBXFileSystemSynchronizedRootGroup from attributes: {"isa">"PBXFileSystemSynchro…...