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

数据结构体--5.0图

目录

一、定义

二、图的顶点与边之间的关系

三、图的顶点与边之间的关系

四、连通图

 五、连通图的生成树定义


 

一、定义

        图(Graph)是由顶点的又穷非空集合合顶点之间边的集合组成,通常表示为:G(V,E),其中,G表示一个图,V表示图G中定点的集合,E是图G中边的集合。

——线性表中我们把数据元素叫元素,树中叫结点,在图中数据元素我们则称之为定点(Vertex)。

——线性表可以没有数据元素,称为空表,树中可以没有结点,叫做空树,而图中的定点集合是有穷非空的。(国外是允许空的)

——线性表中,相邻的数据元素之间具有线性关系,数据结构中,相邻两层的结点具有层次关系,而图结构中,任意两个顶点之间都可能有关系,定点之间的逻辑关系用边来表示,边集是可以为空的。

1、无向边:若顶点Vi到Vj之间的边没有方向,则称这条边为无向边(Edge),用无序偶(Vi,Vj)来表示。

 上图G1是一个无向图,G1={V1,E1},其中

——V1 = {A,B,C,D}

——E1 = {(A,C),(B,C),(C,D),(D,A),(A,C)}

2、有向边:若从定点Vi到Vj的边有方向,则称这条边为有向边,也成为弧(Arc),用有序偶<vi,Vj>来表示,Vi称为弧尾,Vj称为弧头。

上图G2是一个有向图,G2={V2,E2},其中

——V2 = {A,B,C,D}

——E2 = {<B,A>,<B,C>,<C,A>,<A,D>}

二、图的顶点与边之间的关系

1、对于无向图G=(V,E),如果边(V1,V2)∈E,则称顶点V1和V2互为邻接点(Adjacent),即V1和V2相邻接。边(V1,V2)依附(incident)于顶点V1和V2,或者说边(V1,V2)与顶点V1和V2相关联。

2、顶点V的度(Degree)是和V相关联的边的数目,记为TD(V),如下图,顶点A与B互为邻接点,bian(A,B)依附于顶点A与B上,顶点A的度为3.

 

三、图的顶点与边之间的关系

1、对于有向图G=(V,E),如果边<V1,V2>∈E,则称顶点V1邻接到顶点V2,顶点V2邻接自顶点V1。

2、以顶点V为头的弧的数目称为V的入度(InDegree),记为ID(V),以V为尾的弧的数目称为V

的出度(OutDegree),记为OD(V),因此顶点V的度为TD(V)=ID(V)+OD(V)。

3、下图顶点A的入度是2,出度是1,所以顶点A的度是3。

四、连通图

1、在无向图G中,如果从顶点V1到顶点V2有路径,则称V1和V2是连通图,弱国对于图中任意两个顶点Vi和Vj都是连同的,则称G是连通图(ConnectedGraph)。

2、无向图中的极大连通子图称为连通分量。

3、注意:

——首先要是子图,并且子图是要连通的;

——连通子图含有极大顶点数;

——具有极大顶点数的连通子图包含依附于这些顶点的所有边。

 4、在有向图G中,如果对于每一对Vi到V都存在路径,则称G是强连通图。

5、有向图中的极大强连通子图称为有向图的强连通分量。

如下,左侧不是,右侧是

 五、连通图的生成树定义

所谓的一个连通图的生成树是一个极小的连通子图,它含有图中全部的n个顶点,但只有足以构成一棵树的n-1跳边。

相关文章:

数据结构体--5.0图

目录 一、定义 二、图的顶点与边之间的关系 三、图的顶点与边之间的关系 四、连通图 五、连通图的生成树定义 一、定义 图&#xff08;Graph&#xff09;是由顶点的又穷非空集合合顶点之间边的集合组成&#xff0c;通常表示为&#xff1a;G&#xff08;V&#xff0c;E&…...

深入剖析 Golang 程序启动原理 - 从 ELF 入口点到GMP初始化到执行 main!

大家好&#xff0c;我是飞哥&#xff01; 在过去的开发工作中&#xff0c;大家都是通过创建进程或者线程来工作的。Linux进程是如何创建出来的&#xff1f; 、聊聊Linux中线程和进程的联系与区别&#xff01; 和你的新进程是如何被内核调度执行到的&#xff1f; 这几篇文章就是…...

C语言——多文件编程

多文件编程 把函数声明放在头文件xxx.h中&#xff0c;在主函数中包含相应头文件在头文件对应的xxx.c中实现xxx.h声明的函数 防止头文件重复包含 当一个项目比较大时&#xff0c;往往都是分文件&#xff0c;这时候有可能不小心把同一个头文件 include 多次&#xff0c;或者头…...

Git学习part1

02.尚硅谷_Git&GitHub_为什么要使用版本控制_哔哩哔哩_bilibili 1.Git必要性 记录代码开发的历史状态 &#xff0c;允许很多人同时修改文件&#xff08;分布式&#xff09;且不会丢失记录 2.版本控制工具应该具备的功能 1&#xff09;协同修改 多人并行不悖的修改服务器端…...

2309C++均为某个类型

#include <常用> 构 A{空 f(){打印("啊");} }; 元<类 T>构 是点啊:假型{}; 元<>构 是点啊<A>:真型{}; 元<类 T>概念 是呀是点啊<T>::值;元<是呀...T>空 f(T&...t){(t.f(),...); }//均为元<类...T>要求 均为值&l…...

2023年打脸面试官之TCP--瞬间就懂

1.TCP 三次握手之为什么要三次呢&#xff1f;事不过三&#xff1f; 过程如下图&#xff1a; 先来解释下上述的各个标志的含义 序列号seq&#xff1a;占4个字节&#xff0c;用来标记数据段的顺序&#xff0c;TCP把连接中发送的所有数据字节都编上一个序号&#xff0c;第一个字节…...

设计模式-单例模式Singleton

单例模式 单例模式 (Singleton) (重点)1) 为什么要使用单例2) 如何实现一个单例2.a) 饿汉式2.b) 懒汉式2.c) 双重检查锁2.d) 静态内部类2.e) 枚举类2.f) 反射入侵2.g) 序列化与反序列化安全 3) 单例存在的问题3.a) 无法支持面向对象编程 单例模式 (Singleton) (重点) 一个类只…...

PPPoE连接无法建立的排查和修复

嗨&#xff0c;亲爱的读者朋友们&#xff01;你是否曾经遇到过PPPoE连接无法建立的问题&#xff1f;今天我将为你详细解析排查和修复这个问题的步骤。 检查物理连接 首先&#xff0c;我们需要确保物理连接没有问题。请按照以下步骤进行检查&#xff1a; - 检查网线是否插好&…...

QT 发布软件基本操作

一、配置环境变量 找到Qt安装时的bin目录的路径&#xff1a;D:\Qt\Qt5.14.2\5.14.2\mingw73_64\bin&#xff0c;将目录拷贝至下述环境变量中。 打开计算机的高级系统设置 选中环境变量-->系统变量-->Path 点击编辑-->新建-->粘贴 二、生成发布软件的可执行程序 …...

CTFhub-SSRF-内网访问

CTFHub 环境实例 | 提示信息 http://challenge-8bf41c5c86a8c5f4.sandbox.ctfhub.com:10800/?url_ 根据提示&#xff0c;在url 后门添加 127.0.0.1/flag.php http://challenge-8bf41c5c86a8c5f4.sandbox.ctfhub.com:10800/?url127.0.0.1/flag.php ctfhub{a6bb51530c8f6be0…...

Cenos7安装小火车程序动画

运维Shell脚本小试牛刀(一) 运维Shell脚本小试牛刀(二) 运维Shell脚本小试牛刀(三)::$(cd $(dirname $0)&#xff1b; pwd)命令详解 运维Shell脚本小试牛刀(四): 多层嵌套if...elif...elif....else fi_蜗牛杨哥的博客-CSDN博客 Cenos7安装小火车程序动画 一&#xff1a;替换…...

Node 执行命令时传参 process.argv

process 对象是一个全局变量&#xff0c;提供当前 Node.js 进程的有关信息&#xff0c;以及控制当前 Node.js 进程。 因为是全局变量&#xff0c;所以无需使用 require()。 process.argv 属性返回一个数组&#xff0c;这个数组包含了启动Node.js进程时的命令行参数&#xff0c…...

【Vue】快速上手--Vue 3.0

什么是 Vue&#xff1f;​ Vue (发音为 /vjuː/&#xff0c;类似 view) 是一款用于构建用户界面的 JavaScript 框架。它基于标准 HTML、CSS 和 JavaScript 构建&#xff0c;并提供了一套声明式的、组件化的编程模型&#xff0c;帮助你高效地开发用户界面。无论是简单还是复杂的…...

PyTorch深度学习遥感影像地物分类与目标检测、分割及遥感影像问题深度学习优化实践技术应用

我国高分辨率对地观测系统重大专项已全面启动&#xff0c;高空间、高光谱、高时间分辨率和宽地面覆盖于一体的全球天空地一体化立体对地观测网逐步形成&#xff0c;将成为保障国家安全的基础性和战略性资源。未来10年全球每天获取的观测数据将超过10PB&#xff0c;遥感大数据时…...

04、添加 com.fasterxml.jackson.dataformat -- jackson-dataformat-xml 依赖报错

Correct the classpath of your application so that it contains a single, compatible version of com.fasterxml.jackson.dataformat.xml.XmlMapper 解决&#xff1a; 改用其他版本&#xff0c;我没写版本号&#xff0c;springboot自己默认的是 2.11.4 版本 成功启动项目…...

禅道项目管理系统 - 操作使用 (2023版)

1. 部门-用户-权限 新增部门 新增用户 设置权限 2. 项目集创建 项目集 - 添加项目集 3. 产品线创建 产品 - 产品线 4. 产品创建 产品 - 产品列表 - 添加产品 5. 产品计划创建 产品 - xx产品 - 计划 - 创建计划 我这里创建3个计划 (一期, 二期, 三期) 6. 研发需求 - 创建模块…...

C++的多重继承

派生类都只有一个基类,称为单继承(Single Inheritance)。除此之外,C++也支持多继承(Multiple Inheritance),即一个派生类可以有两个或多个基类。 多继承容易让代码逻辑复杂、思路混乱,一直备受争议,中小型项目中较少使用,后来的 Java、C#、PHP 等干脆取消了多继承。 …...

ZooKeeper与Paxos

Apache ZooKeeper是由Apache Hadoop的子项目发展而来&#xff0c;于2010年11月正式成为了Apache的顶级项目。ZooKeeper为分布式应用提供了高效且可靠的分布式协调服务&#xff0c;提供了诸如统一命名服务、配置管理和分布式锁等分布式的基础服务。在解决分布式数据一致性方面&a…...

Cargo 静态编译

git clone --recursive https://github.com/kornelski/pngquant.git vi ~/.cargo/config.toml[http] debug true proxy "127.0.0.1:1080" 1.apt 更新 2.apt install cargo 3.修改源码的Cargo.toml [source.crates-io] #registry "https://code.aliyun.com…...

【多线程】有两个线程都能访问n,初始时n为0,⼀个线程执⾏n++,n+=2,另⼀个线程执⾏n+=3,当两个线程都执行完后n可能的值

必备知识点&#xff1a;n 在底层是由三条指令在CPU完成的 load : 将内存的值读取到CPU寄存器add : 将CPU寄存器中的值进行1操作save : 将CPU寄存器中的值写回内容 回答 首先n操作在底层是由三条指令在CPU完成的&#xff0c;先要将内存中n的值读取到CPU寄存器&#xff0c;然后…...

UE5 学习系列(二)用户操作界面及介绍

这篇博客是 UE5 学习系列博客的第二篇&#xff0c;在第一篇的基础上展开这篇内容。博客参考的 B 站视频资料和第一篇的链接如下&#xff1a; 【Note】&#xff1a;如果你已经完成安装等操作&#xff0c;可以只执行第一篇博客中 2. 新建一个空白游戏项目 章节操作&#xff0c;重…...

day52 ResNet18 CBAM

在深度学习的旅程中&#xff0c;我们不断探索如何提升模型的性能。今天&#xff0c;我将分享我在 ResNet18 模型中插入 CBAM&#xff08;Convolutional Block Attention Module&#xff09;模块&#xff0c;并采用分阶段微调策略的实践过程。通过这个过程&#xff0c;我不仅提升…...

Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility

Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility 1. 实验室环境1.1 实验室环境1.2 小测试 2. The Endor System2.1 部署应用2.2 检查现有策略 3. Cilium 策略实体3.1 创建 allow-all 网络策略3.2 在 Hubble CLI 中验证网络策略源3.3 …...

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

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

2025 后端自学UNIAPP【项目实战:旅游项目】6、我的收藏页面

代码框架视图 1、先添加一个获取收藏景点的列表请求 【在文件my_api.js文件中添加】 // 引入公共的请求封装 import http from ./my_http.js// 登录接口&#xff08;适配服务端返回 Token&#xff09; export const login async (code, avatar) > {const res await http…...

实现弹窗随键盘上移居中

实现弹窗随键盘上移的核心思路 在Android中&#xff0c;可以通过监听键盘的显示和隐藏事件&#xff0c;动态调整弹窗的位置。关键点在于获取键盘高度&#xff0c;并计算剩余屏幕空间以重新定位弹窗。 // 在Activity或Fragment中设置键盘监听 val rootView findViewById<V…...

【Java学习笔记】BigInteger 和 BigDecimal 类

BigInteger 和 BigDecimal 类 二者共有的常见方法 方法功能add加subtract减multiply乘divide除 注意点&#xff1a;传参类型必须是类对象 一、BigInteger 1. 作用&#xff1a;适合保存比较大的整型数 2. 使用说明 创建BigInteger对象 传入字符串 3. 代码示例 import j…...

第7篇:中间件全链路监控与 SQL 性能分析实践

7.1 章节导读 在构建数据库中间件的过程中&#xff0c;可观测性 和 性能分析 是保障系统稳定性与可维护性的核心能力。 特别是在复杂分布式场景中&#xff0c;必须做到&#xff1a; &#x1f50d; 追踪每一条 SQL 的生命周期&#xff08;从入口到数据库执行&#xff09;&#…...

深入浅出Diffusion模型:从原理到实践的全方位教程

I. 引言&#xff1a;生成式AI的黎明 – Diffusion模型是什么&#xff1f; 近年来&#xff0c;生成式人工智能&#xff08;Generative AI&#xff09;领域取得了爆炸性的进展&#xff0c;模型能够根据简单的文本提示创作出逼真的图像、连贯的文本&#xff0c;乃至更多令人惊叹的…...

spring Security对RBAC及其ABAC的支持使用

RBAC (基于角色的访问控制) RBAC (Role-Based Access Control) 是 Spring Security 中最常用的权限模型&#xff0c;它将权限分配给角色&#xff0c;再将角色分配给用户。 RBAC 核心实现 1. 数据库设计 users roles permissions ------- ------…...