#笨鸟先飞# 数据结构与算法基础 课程笔记 第六章 图
图的定义和基本术语
图:G=( V , E ) Graph=(Vertex,Edge)
V:顶点(数据元素)的有穷非空集合;
E:边的有穷集合。
无向图:每条边都是无方向的
有向图:每条边都是有方向的

完全图:任意两个顶点都有一条边相连

稀疏图:有很少边或弧的图(e<n logn)
稠密图:有较多边或弧的图
网:边或弧带权的图
邻接:有边或弧相连的两个顶点之间的关系
存在(v1,v2),则称v1和v2互为邻接点;
存在<v1,v2>,则称v1邻接到v2,v2邻接于v1。
关联(依附):边或弧与顶点之间的关系;存在(v1,v2)或<v1,v2>,则称该边或弧关联于v1和v2
顶点的度:与该顶点相关联的边的数目,记为TD(v)
在有向图中,顶点的度等于该顶点的入度与出度之和;
顶点v的入度是以v为终点的有向边的条数,记作ID(v);
顶点v的出度是以v为始点的有向边的条数,记作OD(v)。
路径:接续的边构成的顶点序列
路径长度:路径上的边或弧的数目或权值之和
回路(环):第一个顶点和最后一个顶点相同的路径
简单路径:除路径起点和终点可以相同外,其余顶点均不相同的路径
简单回路(简单环):除路径起点和终点相同外,其余顶点均不相同的回路

连通图(强连通图):在无(有)向图G=(V,E)中,若对任何两个顶点v、u都存在从v到u的路径,则称G是连通图(强连通图)。

子图:

连通分量:无向图G的极大连通子图·称为G的连通分量。
极大连通子图的意思是:该子图是G的连通子图,将G的任何不在该子图中的顶点加入,子图不再连通。

强连通分量:有向图G的极大强连通子图称为G的强连通分量。
极大强连通子图的意思是:该子图是G的强连通子图,将G的任何不在该子图中的顶点加入,子图就不再是强连通的。

极小连通子图:该子图是G的连通子图,在该子图中删除任何一条边,该子图不再连通。
生成树:包含无向图G所有顶点的极小连通子图

生成树林:对非连通图,由各个连通分量的生成树组成的集合
图的类型定义
图的抽象数据类型定义

图的基本操作


图的存储结构
相关文章:
#笨鸟先飞# 数据结构与算法基础 课程笔记 第六章 图
图的定义和基本术语图:G( V , E ) Graph(Vertex,Edge)V:顶点(数据元素)的有穷非空集合;E:边的有穷集合。无向图:每条边都是无方向的有向图:每条边…...
深入浅出带你学习Apache中间件常见漏洞
前言 上一篇文章给大家总结了一下IIS中间件的漏洞,这篇文章就给大家讲一下apache中间件漏洞,说起apache大家一定不会陌生,这是我们日常中经常用到的中间件,下面由我来给大家讲解一下改中间件常见的漏洞。 Apache是什么ÿ…...
用多种指针方法访问数据元素,实现逆序输出
这里注意下数组指针的下标表示: 我们已经知道,数组名a总是指向a[0]的指针,*(ai)是对a[i]的引用,实际上,编译器中,对数组的引用,如a[i],总是被编译器改写成*(ai)的形式。 另外说明下…...
WebDAV之葫芦儿·派盘+NMM
NMM 支持WebDAV方式连接葫芦儿派盘。 推荐一款文件管理器,可以对手机中的文件进行多方面的管理,支持语法高亮和ftp等远程的文件的管理。支持从WebDav服务器连接葫芦儿派盘服务下载文件和上传文件。 NMM文本编辑器是一款文件管理器,在功能上面更加的适合于一些编程人员进行使…...
Redis多级缓存
文章目录一. 什么是多级缓存二. JVM进程缓存一. 什么是多级缓存 传统的缓存策略一般是请求到达Tomcat后,先查询Redis,如果未命中则查询数据库,如图: 存在下面的问题: 请求要经过Tomcat处理,Tomcat的性能…...
【原创】java+swing+mysql会议室管理系统设计与实现
本文主要介绍使用javaswingmysql等技术去设计完成一个企业公司的会议室管理系统,帮助企业员工去进行会议室的预约安排。 功能分析: 会议室管理系统的使用角色,一般分为管理员和员工用户,管理员进行数据管理,员工进行…...
【Redis】Redis 常用数据类型操作 ① ( 数据库操作 | Redis 数据库连接参数 | Redis 数据库个数 | Redis 访问机制 )
文章目录一、Redis 数据库连接参数二、Redis 数据库个数三、Redis 访问机制一、Redis 数据库连接参数 连接 Redis 数据库 , 只需要 IP 地址 , 端口号 , 访问密码 即可 , 如果没有 设置 访问密码 可忽略该选项 ; Redis 默认端口号是 6379 ; 参考 【Redis】Redis 数据库 安装、…...
GAMES101-计算机图形学入门 LEC4: TRANSFORMATION-3D
本节课程视频地址:https://www.bilibili.com/video/BV1X7411F744/?p4 补充上一节课的一个内容,旋转矩阵的逆矩阵是它的转置,也就是说有R−θRθ−1RθTR_{-\theta} R_\theta^{-1}R_\theta^TR−θRθ−1RθT 上节课讲了,…...
robot实战:截取字符串
一:变量标识符号(1) Scalar型变量: "$"作为标识符号,例如:${var}, 这个打印log时只能用logset赋值:a: ${var} Set Variable abcb:${var2} Set Variable If ${Var}abc efgh ace 如果var的值和abc相等…...
【面经】滴滴测开一面
滴滴测开一面 面试官自我介绍面试者自我介绍大概实习多久?你在在校经历比较丰富,说一下打ACM那些比赛中的一些经验,找一些具体的项目说一下在打ACM中团队里几个人? 你负责什么?在上段实习的过程中都做了哪些事情&…...
数据治理-主数据
二、某企业集团旗下有房地产、供应链、物流、酒店等多个业务子公司,为了统一管理,集团推进数字化转型,建立了统一的数据仓库,各子公司将数据集成到集团信息部负责管理的 数据平台。集团在实施数据治理过程中,发现各业务…...
软考-中级-软件设计师-成绩
低分飘过,备考经验主要就是刷题。...
学习笔记<二> MySQL学习(3):分库、分表
文章目录为什么分库分表一、垂直分片、水平分片二、常用的数据分片策略三、垂直分表、垂直分库、水平分库、水平分表四、垂直切分、水平切分优缺点五、数据分片规则六、分库分表带来的问题本文参考博主「小Y是我的」的文章,原文链接:https://blog.csdn.n…...
重生之我是赏金猎人-SRC漏洞挖掘(八)-记一次移花接木的GetShell
0x00:前言 https://github.com/J0o1ey/BountyHunterInChina 欢迎亲们点个star 作者:RGM78sec 某天测厂商业务时,发现其中有一个提供音乐播放业务的资产,正好里面有我想听的歌,于是就有了这篇文章 0x01:…...
离线数仓(五):数仓搭建
文章目录一、创建数据库二、ODS 层(原始数据层)三、DWD 层(明细数据层)3.1 get_json_object 函数使用3.2 启动日志表 DWD层创建四、DWS 层(服务数据层)五、DWT 层(数据主题层)六、AD…...
安装SQL Server2017 过程中报KB29119355失败的解决方案
SQLServer 2017脱机版下载地址:http://download.microsoft.com/download/6/4/A/64A05A0F-AB28-4583-BD7F-139D0495E473/SQLServer2017-x64-CHS-Dev.isoMicrosoft SQL Server Management Studio 18管理工具下载https://learn.microsoft.com/zh-cn/sql/ssms/download-…...
2023年浙江建筑特种工(施工升降机)真题题库及答案
百分百题库提供特种工(施工升降机)考试试题、特种工(施工升降机)考试预测题、特种工(施工升降机)考试真题、特种工(施工升降机)证考试题库等,提供在线做题刷题,在线模拟考…...
2023年进入互联网行业好找工作吗?
俗话说:选择大于努力。年后求职小高峰,大家在找工作的时候选择肯定也多了。说真,不是人人都有铁饭,普通家庭的孩子想要在2023年进入互联网行业去找工作可能吗?01有一点大家要清楚,2022年是进入过一个寒冬的…...
基于策略模式企业实战中策略命中设计
背景 在公司实际项目项目开发中,有一个策略命中的开发需求。根据用户请求参数的不同来动态返回不同的业务数据。比如说有城市、客户年龄、请求时间3个策略维度,不同的城市返回不同的地区的地标,根据时间地标的背景色要发生变化等等的需求。当…...
pod生命周期,pod控制器service
一:pod-demo.yml apiVersion: v1 # <string> kind: Pod # <string> metadata: # <Object>对象:键值对的集合,又称为映射(mapping)/ 哈希(hashes) / 字…...
IGP(Interior Gateway Protocol,内部网关协议)
IGP(Interior Gateway Protocol,内部网关协议) 是一种用于在一个自治系统(AS)内部传递路由信息的路由协议,主要用于在一个组织或机构的内部网络中决定数据包的最佳路径。与用于自治系统之间通信的 EGP&…...
vscode(仍待补充)
写于2025 6.9 主包将加入vscode这个更权威的圈子 vscode的基本使用 侧边栏 vscode还能连接ssh? debug时使用的launch文件 1.task.json {"tasks": [{"type": "cppbuild","label": "C/C: gcc.exe 生成活动文件"…...
Java多线程实现之Callable接口深度解析
Java多线程实现之Callable接口深度解析 一、Callable接口概述1.1 接口定义1.2 与Runnable接口的对比1.3 Future接口与FutureTask类 二、Callable接口的基本使用方法2.1 传统方式实现Callable接口2.2 使用Lambda表达式简化Callable实现2.3 使用FutureTask类执行Callable任务 三、…...
Linux-07 ubuntu 的 chrome 启动不了
文章目录 问题原因解决步骤一、卸载旧版chrome二、重新安装chorme三、启动不了,报错如下四、启动不了,解决如下 总结 问题原因 在应用中可以看到chrome,但是打不开(说明:原来的ubuntu系统出问题了,这个是备用的硬盘&a…...
大模型多显卡多服务器并行计算方法与实践指南
一、分布式训练概述 大规模语言模型的训练通常需要分布式计算技术,以解决单机资源不足的问题。分布式训练主要分为两种模式: 数据并行:将数据分片到不同设备,每个设备拥有完整的模型副本 模型并行:将模型分割到不同设备,每个设备处理部分模型计算 现代大模型训练通常结合…...
Spring AI 入门:Java 开发者的生成式 AI 实践之路
一、Spring AI 简介 在人工智能技术快速迭代的今天,Spring AI 作为 Spring 生态系统的新生力量,正在成为 Java 开发者拥抱生成式 AI 的最佳选择。该框架通过模块化设计实现了与主流 AI 服务(如 OpenAI、Anthropic)的无缝对接&…...
如何理解 IP 数据报中的 TTL?
目录 前言理解 前言 面试灵魂一问:说说对 IP 数据报中 TTL 的理解?我们都知道,IP 数据报由首部和数据两部分组成,首部又分为两部分:固定部分和可变部分,共占 20 字节,而即将讨论的 TTL 就位于首…...
搭建DNS域名解析服务器(正向解析资源文件)
正向解析资源文件 1)准备工作 服务端及客户端都关闭安全软件 [rootlocalhost ~]# systemctl stop firewalld [rootlocalhost ~]# setenforce 0 2)服务端安装软件:bind 1.配置yum源 [rootlocalhost ~]# cat /etc/yum.repos.d/base.repo [Base…...
NPOI操作EXCEL文件 ——CAD C# 二次开发
缺点:dll.版本容易加载错误。CAD加载插件时,没有加载所有类库。插件运行过程中用到某个类库,会从CAD的安装目录找,找不到就报错了。 【方案2】让CAD在加载过程中把类库加载到内存 【方案3】是发现缺少了哪个库,就用插件程序加载进…...
Linux部署私有文件管理系统MinIO
最近需要用到一个文件管理服务,但是又不想花钱,所以就想着自己搭建一个,刚好我们用的一个开源框架已经集成了MinIO,所以就选了这个 我这边对文件服务性能要求不是太高,单机版就可以 安装非常简单,几个命令就…...
