当前位置: 首页 > 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 提取码&…...

React 第五十五节 Router 中 useAsyncError的使用详解

前言 useAsyncError 是 React Router v6.4 引入的一个钩子&#xff0c;用于处理异步操作&#xff08;如数据加载&#xff09;中的错误。下面我将详细解释其用途并提供代码示例。 一、useAsyncError 用途 处理异步错误&#xff1a;捕获在 loader 或 action 中发生的异步错误替…...

RocketMQ延迟消息机制

两种延迟消息 RocketMQ中提供了两种延迟消息机制 指定固定的延迟级别 通过在Message中设定一个MessageDelayLevel参数&#xff0c;对应18个预设的延迟级别指定时间点的延迟级别 通过在Message中设定一个DeliverTimeMS指定一个Long类型表示的具体时间点。到了时间点后&#xf…...

Golang 面试经典题:map 的 key 可以是什么类型?哪些不可以?

Golang 面试经典题&#xff1a;map 的 key 可以是什么类型&#xff1f;哪些不可以&#xff1f; 在 Golang 的面试中&#xff0c;map 类型的使用是一个常见的考点&#xff0c;其中对 key 类型的合法性 是一道常被提及的基础却很容易被忽视的问题。本文将带你深入理解 Golang 中…...

基于ASP.NET+ SQL Server实现(Web)医院信息管理系统

医院信息管理系统 1. 课程设计内容 在 visual studio 2017 平台上&#xff0c;开发一个“医院信息管理系统”Web 程序。 2. 课程设计目的 综合运用 c#.net 知识&#xff0c;在 vs 2017 平台上&#xff0c;进行 ASP.NET 应用程序和简易网站的开发&#xff1b;初步熟悉开发一…...

Python爬虫实战:研究feedparser库相关技术

1. 引言 1.1 研究背景与意义 在当今信息爆炸的时代,互联网上存在着海量的信息资源。RSS(Really Simple Syndication)作为一种标准化的信息聚合技术,被广泛用于网站内容的发布和订阅。通过 RSS,用户可以方便地获取网站更新的内容,而无需频繁访问各个网站。 然而,互联网…...

从深圳崛起的“机器之眼”:赴港乐动机器人的万亿赛道赶考路

进入2025年以来&#xff0c;尽管围绕人形机器人、具身智能等机器人赛道的质疑声不断&#xff0c;但全球市场热度依然高涨&#xff0c;入局者持续增加。 以国内市场为例&#xff0c;天眼查专业版数据显示&#xff0c;截至5月底&#xff0c;我国现存在业、存续状态的机器人相关企…...

Qwen3-Embedding-0.6B深度解析:多语言语义检索的轻量级利器

第一章 引言&#xff1a;语义表示的新时代挑战与Qwen3的破局之路 1.1 文本嵌入的核心价值与技术演进 在人工智能领域&#xff0c;文本嵌入技术如同连接自然语言与机器理解的“神经突触”——它将人类语言转化为计算机可计算的语义向量&#xff0c;支撑着搜索引擎、推荐系统、…...

Unit 1 深度强化学习简介

Deep RL Course ——Unit 1 Introduction 从理论和实践层面深入学习深度强化学习。学会使用知名的深度强化学习库&#xff0c;例如 Stable Baselines3、RL Baselines3 Zoo、Sample Factory 和 CleanRL。在独特的环境中训练智能体&#xff0c;比如 SnowballFight、Huggy the Do…...

深入解析C++中的extern关键字:跨文件共享变量与函数的终极指南

&#x1f680; C extern 关键字深度解析&#xff1a;跨文件编程的终极指南 &#x1f4c5; 更新时间&#xff1a;2025年6月5日 &#x1f3f7;️ 标签&#xff1a;C | extern关键字 | 多文件编程 | 链接与声明 | 现代C 文章目录 前言&#x1f525;一、extern 是什么&#xff1f;&…...

C++八股 —— 单例模式

文章目录 1. 基本概念2. 设计要点3. 实现方式4. 详解懒汉模式 1. 基本概念 线程安全&#xff08;Thread Safety&#xff09; 线程安全是指在多线程环境下&#xff0c;某个函数、类或代码片段能够被多个线程同时调用时&#xff0c;仍能保证数据的一致性和逻辑的正确性&#xf…...