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

24数据结构-图的基本概念与存储结构

目录

  • 第六章 图
  • 6.1 图的基本概念
      • 知识回顾
  • 6.2 图的储存结构(邻接矩阵法)
    • 1. 数组表示法
      • (1) 有向图,无向图的邻接矩阵
    • 2. 定义邻接矩阵的结构
    • 3. 定义图的结构
    • 4. 构造图G
    • 5. 特点

第六章 图

6.1 图的基本概念

图是一种非线性结构
在这里插入图片描述

图的特点:

  • 顶点之间的关系是任意的
  • 图中任意两个顶点之间都可能相关
  • 顶点的前驱和后继个数无限制
  1. 定义:图是一种数据元素间存在多对多关系的数据结构加上一组基本操作构成的抽象数据类型
  • 定义:图G由顶点集V和边集E组成,记为G=(V,E),其中V(G)表示图G中顶点的有限非空集;E(G)表示图G中顶点之间的关系(边)集合。若V={V1,V2,……Vn},则用|V|表示图G中顶点的个数,也称图G的阶,E={(u,v)|u∈V,v∈V},用|E|表示图G中边的条数。
  • 注意:线性表可以是空表,树可以是空树,但图不可以为空,即V一定是非空集
  • 弧头和弧尾
    <x,y>表示从顶点到顶点y的一条弧,并称x为弧尾或起始点,称y为弧头或终端点
  1. 无向图,有向图:有向图<u,v>,其中u表示弧尾,v表示弧头
  2. 简单图:简单图:①不存在重复边,② 不存在顶点到自身的边
  3. 多重图:图G中某两个结点之间的边数多于一条,又允许顶点通过同一条边和自己关联,则G为多重图。
  4. 度,入度,出度:① 无向图:在具有n个顶点,e条边的无向图中,全部顶点的度的和等于边数的2倍(一条边连两个顶点,所以一条边两个度)。②有向图:度之和入度+出度(一条边一个出度一个入度),在具有n个顶点,e条边的有向图中,入度=出度=e
  5. 路径,简单路径,路径长度:① 在路径序列中,顶点不重复出现的路径称为简单路径。②路径长度:路径上边的数目(简单就意味着顶点不重复)。
  6. 回路,简单回路:除第一个顶点和最后一个顶点外,其余顶点不重复出现的回路称为简单回路。
  7. 点到点到距离:从顶点u出发到顶点v的最短路径若存在,则此路径的长度称为u到v的距离。若u到v根本不存在路径,则记该距离为无穷(∞)
  8. 连通图,强连通图:①若图G中任意两个顶点都是连通的,则称图G为连通图(无向图中的连通就是两个顶点之间路径存在;有向图中的强连通是两个顶点之间存在往返的路径,就是w到v和v到w都有路径,强连通是有向图独有的概念),否则称为非连通图。对于n个顶点的无向图G,若G是连通图,则至少有n-1条边(就是把每个顶点都连线一个顶点,就存在路径了),若G是非连通图,则最多可能有 C n − 1 2 C_{n-1}^{2} Cn12,(就是除去一个顶点,其他顶点两两相连,只要不连接最后一个顶点,这个图就是不连通的最极端情况)。②若图中任何一项顶点都是强连通的,则称为图为强连通图。对于n个顶点的有向图G,若G是强连通图,则最少为n条边(形成回路)。
  9. 连通的补充图解:
  • 连通的最少边数:
    在这里插入图片描述
  • 不连通的最多边数:
    在这里插入图片描述
  • 强连通的最少边数
    在这里插入图片描述
  1. 子图(不用包含所有顶点)、生成子图:若包含所有顶点的子图,就称为生成子图。并不是任意几个点,任意几条边都能构成子图(例如不构成图的情况)。
    在这里插入图片描述

  2. 连通分量:无向图中极大连通子图(子图必须连通,且包含尽可能多的顶点和边)称为连通分量。
    在这里插入图片描述

  3. 强连通分量:有向图中有极大强连通子图(子图必须强连通,同时保留尽可能多的边)称为有向图的强连通分量。
    在这里插入图片描述

  4. 生成树:连通图的生成树是包含图中全部顶点的一个极小连通子图边尽可能的小,但要保持连通若图中顶点数是n,则它的生成树含有n-1条边,对于生成树而言,若砍去一条边,则会变成非连通图,若加上一条边则会形成一个回路(环)

  5. 生成森林:在非连通图中,连通分量的生成树构成了非连通图的生成森林
    在这里插入图片描述

  6. 边的权,带权图(网)
    在这里插入图片描述

  7. 无向完全图:无向图中任意两个顶点之间都存在边。

  8. 有向完全图:有向图中任意两个顶点之间都存在方向相反的两条弧。
    在这里插入图片描述

  9. 稀疏图,稠密图:这二者是相对的
    在这里插入图片描述

  10. 树:不存在回路,且连通的无向图,n个顶点的树,必有n-1条边。

  11. 有向树:一个顶点的入度为0,其余顶点的入度均有1的有向图,称为有向树。
    n个顶点的图,若|E|>n-1,则一定有回路。
    在这里插入图片描述

知识回顾

在这里插入图片描述

6.2 图的储存结构(邻接矩阵法)

在这里插入图片描述

1. 数组表示法

(1) 有向图,无向图的邻接矩阵

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

① 对于无向图,顶点vi的度是邻接矩阵中第i行(或第i列)的元素之和, TD(vi)= ∑ a[i][j]。
② 对于有向图,顶点VI的出度OD(vi)是邻接矩阵中第i行的元素之和顶点vi的出度ID(vi)是邻接矩阵中第j列)的元素之和
邻接矩阵法求顶点的度。入度。出度的时间复杂度为O(|V|)

在这里插入图片描述

2. 定义邻接矩阵的结构

#define INFINITY INT_MAX
#define MAX_VERTEXT_NUM 20
typedef enum{DG,DN,AG,AN}GraphKind;
typedef struct ArcCell{VRType adj;//对无向图,用0,1表示是否相邻,对于带权图,为权值InfoType *info;//该弧相关信息的指针}RrcCell,AdjMatrix[MAX_VERTEXT_NUM][MAX_VERTEXT_NUM];//邻接矩阵

3. 定义图的结构

(1)代码:

//定义图的结构
typedef struct {VertextType exs[MAX_VERTEXT_NUM]; //顶点AdjMatrix arcs[MAX_VERTEXT_NUM][MAX_VERTEXT_NUM]; //边的邻接矩阵int vexnum,arcnum; //个数GraphKind kind;//有向图?无向图?
}MGraph;

在这里插入图片描述

4. 构造图G

status CreateGraph(MGraph &G)
{scanf(&G.kind){case DG:return CreateDG(G);case DN:return CreateDN(G);case UDG:return CreateUDG(G);case UDN:return CreateDGN(G);default:return ERROR;}
}
//用无向图为例status CreateUDN(MGraph &G)
{scanf(&G.arcnum,&G.vexnum,&IncInfo);//输入点数和边数//给顶点进行数字化编号for(i=0;i<G.vexnum;i++){ scanf(&G.exs[i]);//定义顶点数组(如果顶点本身就是1~n的数字无需这一步)}//初始化邻接矩阵for(i=0;i<G.vexnum;i++){for(j=0;j<G.vexnum;j++){G.arcs[i][j]={ININITY,NULL};}}//通过边数进行遍历for(k=0;k<G.arcnum;K++){scanf(&V1,&V2,&W);//输入邻接的连个顶点i=locatteVex(G,V1);j=locateVex(G,V2);//查找V1,V2的位置G.arcs[i][j].adj=w;//给邻接矩阵赋值if(IncInfo){INPUT(*G.arcs[i][j].info);}G.arcs[j][i]=G.arcs[i][j];//由于是无向图,对称}return ok;
}

5. 特点

优点:

  • 无向图邻接矩阵是对称矩阵,同一条边表示了两次
  • 顶点v的度:等于二维数组对应行(或列)中1的个数
  • 判断两顶点v、u是否为邻接点:只需判二维数组对应分量是否为1
  • 在图中增加、删除边:只需对二维数组对应分量赋值1或清0
  • 占用存储空间只与它的顶点数有关,与边数无关;适用于边稠密的图
  • 对有向图的数组表示法可做类似的讨论’‘

缺点:

  • 不便于删除和增加顶点(增删边简单)
  • 不便于统计边的数目,需要扫描邻接矩阵所有元素才能统计完毕,时间复杂度为O( n 2 n^2 n2 )
  • 空间复杂度高,对于有向图,n个顶点需要 n 2 n^2 n2 个单元存储边,对于无向图,n(n-1)/2个单元,空间复杂度为O( n 2 n^2 n2 )

相关文章:

24数据结构-图的基本概念与存储结构

目录 第六章 图6.1 图的基本概念知识回顾 6.2 图的储存结构&#xff08;邻接矩阵法&#xff09;1. 数组表示法(1) 有向图&#xff0c;无向图的邻接矩阵 2. 定义邻接矩阵的结构3. 定义图的结构4. 构造图G5. 特点 第六章 图 6.1 图的基本概念 图是一种非线性结构 图的特点&am…...

自然语言处理学习笔记(三)————HanLP安装与使用

目录 1.HanLP安装 2.HanLP使用 &#xff08;1&#xff09;预下载 &#xff08;2&#xff09;测试 &#xff08;3&#xff09;命令行 &#xff08;4&#xff09;测试样例 3.pyhanlp可视化 4. HanLP词性表 1.HanLP安装 HanLP的 Python接口由 pyhanlp包提供&#xff0c;其安装…...

CS 144 Lab Five -- the network interface

CS 144 Lab Five -- the network interface TCP报文的数据传输方式地址解析协议 ARPARP攻击科普 Network Interface 具体实现测试tcp_ip_ethernet.ccTCPOverIPv4OverEthernetAdapterTCPOverIPv4OverEthernetSpongeSocket通信过程 对应课程视频: 【计算机网络】 斯坦福大学CS144…...

Mecha

一、Mecha Mecha 是一个开源的多云 Kubernetes 管理平台&#xff0c;旨在简化和统一在多个云提供商上运行 Kubernetes 集群的管理和操作。它是由阿里巴巴集团开发和维护的项目。 Mecha 的主要目标是提供一个统一的界面和工具&#xff0c;使用户能够更轻松地在不同的云提供商上…...

Apache RocketMQ之集成RocketMQ_MQTT 安装部署协议

Apache RocketMQ 安装说明 安装步骤 参考快速开始 https://rocketmq.apache.org/zh/docs/quickStart/01quickstart 安装可视化rocketmq_dashboard下载地址 https://rocketmq.apache.org/zh/docs/4.x/deployment/03Dashboard/ 安装rocketmq_mqtt https://rocketmq.apache.o…...

Oracle多行数据合并为一行数据,并将列数据转为字段名

Oracle多行数据合并为一行数据 实现查询效果原数据 方式一&#xff1a;MAX()数据效果SQL 方式二&#xff1a;LISTAGG()数据效果 方式三&#xff1a;WM_CONCAT()数据效果 实现查询效果 原数据 FZPROJECTVALUE1电脑$16001手机$121导管$12电脑$22手机$22 方式一&#xff1a;MAX…...

MySQL5.7 与 MariaDB10.1 审计插件兼容性验证

这是一篇关于发现 MariaDB 审计插件导致 MySQL 发生 crash 后&#xff0c;展开适配验证并进行故障处理的文章。 作者&#xff1a;官永强 爱可生DBA 团队成员&#xff0c;擅长 MySQL 运维方面的技能。热爱学习新知识&#xff0c;亦是个爱打游戏的宅男。 本文来源&#xff1a;原创…...

PyTorch Lightning教程五:Debug调试

如果遇到了这样一个问题&#xff0c;当一次训练模型花了好几天&#xff0c;结果突然在验证或测试的时候崩掉了&#xff0c;这个时候其实是很奔溃的&#xff0c;主要还是由于没有提前知道哪些时候会出现什么问题&#xff0c;本节会引入Lightning的Debug方案 1.fast_dev_run参数 …...

末流211无科研保研经验分享

文章目录 个人背景夏令营哈工大威海西工大光电北航软院北邮计算机中科大科学岛 预推免东南软件北航计算机 写在最后心路历程寄语 个人背景 院校&#xff1a;末流211专业背景&#xff1a;计算机科学与技术排名&#xff1a;夏令营7 / 126&#xff0c;预推免3 / 126英语&#xff…...

日期选择器多选换行

<el-form-item label"日期选择"><div class"multi-date-picker"><div class"date-item"><span class"dateIcon"><el-icon><Calendar /></el-icon></span><span class"dateIt…...

NodeJS原型链污染ctfshow_nodejs

文章目录 NodeJS原型链污染&ctfshow_nodejs前言0x01.原型与原型链0x02.prototype和__proto__分别是什么&#xff1f;0x03.原型链继承不同对象的原型链* 0x04.原型链污染原理0x05.merge()导致原型链污染0x06.ejs模板引擎RCEejs模板引擎另一处rce 0x07.jade模板引擎RCE【ctfs…...

18. SpringBoot 如何在 POM 中引入本地 JAR 包

❤️ 个人主页&#xff1a;水滴技术 &#x1f338; 订阅专栏&#xff1a;成功解决 BUG 合集 &#x1f680; 支持水滴&#xff1a;点赞&#x1f44d; 收藏⭐ 留言&#x1f4ac; Spring Boot 是一种基于 Spring 框架的轻量级应用程序开发框架&#xff0c;它提供了快速开发应用程…...

vue2-$nextTick有什么作用?

1、$nextTick是什么&#xff1f; 官方定义&#xff1a;在下次DOM更新循环结束之后执行延迟回调。在修改数据之后立即使用这个方法&#xff0c;获取更新后的DOM。 解释&#xff1a;Vue在更新DOM时是异步执行的&#xff0c;当数据发生变化时&#xff0c;Vue将开启一个异步更新的队…...

python自动收集粘贴板

win10的粘贴板可以用“winV”查看&#xff1a; 每次复制都相当于入栈一个字符串&#xff0c;粘贴相当于获取栈顶。 但是系统自带的这个粘贴板貌似不能一键导出&#xff0c;所以我写了个python代码完成这个功能&#xff1a; import pyperclip import timetmp while True:txt…...

Vue3_语法糖—— <script setup>以及unplugin-auto-import自动引入插件

<script setup>import { ref , onMounted} from vue;let obj ref({a: 1,b: 2,}); let changeObj ()>{console.log(obj)obj.value.c 3 //ref写法}onMounted(()>{console.log(obj)})</script> 里面的代码会被编译成组件 setup() 函数的内容。 相当于 <…...

2023-08-06力扣做过了的题

链接&#xff1a; 剑指 Offer 30. 包含min函数的栈 题意&#xff1a; 如题 解&#xff1a; 初级算法里做过的题 优化是存储和min的差值使得只需要n的栈和一个int min 实际代码&#xff1a; #include<bits/stdc.h> using namespace std; class MinStack { public:…...

进程间通信之管道

文章目录 一、管道1. 匿名管道2. 命名管道 进程具有独立性&#xff0c;因此进程间通信的前提是两个进程能看到同一份资源 一、管道 对于进程打开的内存文件&#xff0c;操作系统是以引用计数的方式创建的 file 结构体&#xff0c;如果让两个进程与同一个 file 结构体关联&…...

f12 CSS网页调试_css样式被划了黑线怎么办

我的问题是这样的 class加上去了,但是样式不生效,此时可能是样式被其他样式覆盖了, 解决方案就是 给颜色后边添加一个!important...

vue-制作自动滚动效果

第一步&#xff1a;下载 可以查看官方地址chenxuan0000 npm i vue-seamless-scroll -save 第二步&#xff1a;引用 import vueSeamlessScroll from "vue-seamless-scroll";//注册components: {vueSeamlessScroll,}, 第三步&#xff1a;使用 <vue-seamless…...

[国产MCU]-BL602-开发实例-DMA数据传输

DMA数据传输 文章目录 DMA数据传输1、DMA介绍2、DMA驱动API介绍3、DMA使用示例DMA(Direct Memory Access)是一种内存存取技术,可以独立地直接读写系统内存,而不需处理器介入处理。 在同等程度的处理器负担下,DMA是一种快速的数据传送方式。 BL602的DMA控制器有4组独立专用通…...

MySQL 隔离级别:脏读、幻读及不可重复读的原理与示例

一、MySQL 隔离级别 MySQL 提供了四种隔离级别,用于控制事务之间的并发访问以及数据的可见性,不同隔离级别对脏读、幻读、不可重复读这几种并发数据问题有着不同的处理方式,具体如下: 隔离级别脏读不可重复读幻读性能特点及锁机制读未提交(READ UNCOMMITTED)允许出现允许…...

【力扣数据库知识手册笔记】索引

索引 索引的优缺点 优点1. 通过创建唯一性索引&#xff0c;可以保证数据库表中每一行数据的唯一性。2. 可以加快数据的检索速度&#xff08;创建索引的主要原因&#xff09;。3. 可以加速表和表之间的连接&#xff0c;实现数据的参考完整性。4. 可以在查询过程中&#xff0c;…...

Python:操作 Excel 折叠

💖亲爱的技术爱好者们,热烈欢迎来到 Kant2048 的博客!我是 Thomas Kant,很开心能在CSDN上与你们相遇~💖 本博客的精华专栏: 【自动化测试】 【测试经验】 【人工智能】 【Python】 Python 操作 Excel 系列 读取单元格数据按行写入设置行高和列宽自动调整行高和列宽水平…...

VTK如何让部分单位不可见

最近遇到一个需求&#xff0c;需要让一个vtkDataSet中的部分单元不可见&#xff0c;查阅了一些资料大概有以下几种方式 1.通过颜色映射表来进行&#xff0c;是最正规的做法 vtkNew<vtkLookupTable> lut; //值为0不显示&#xff0c;主要是最后一个参数&#xff0c;透明度…...

鸿蒙DevEco Studio HarmonyOS 5跑酷小游戏实现指南

1. 项目概述 本跑酷小游戏基于鸿蒙HarmonyOS 5开发&#xff0c;使用DevEco Studio作为开发工具&#xff0c;采用Java语言实现&#xff0c;包含角色控制、障碍物生成和分数计算系统。 2. 项目结构 /src/main/java/com/example/runner/├── MainAbilitySlice.java // 主界…...

论文阅读:LLM4Drive: A Survey of Large Language Models for Autonomous Driving

地址&#xff1a;LLM4Drive: A Survey of Large Language Models for Autonomous Driving 摘要翻译 自动驾驶技术作为推动交通和城市出行变革的催化剂&#xff0c;正从基于规则的系统向数据驱动策略转变。传统的模块化系统受限于级联模块间的累积误差和缺乏灵活性的预设规则。…...

2025年低延迟业务DDoS防护全攻略:高可用架构与实战方案

一、延迟敏感行业面临的DDoS攻击新挑战 2025年&#xff0c;金融交易、实时竞技游戏、工业物联网等低延迟业务成为DDoS攻击的首要目标。攻击呈现三大特征&#xff1a; AI驱动的自适应攻击&#xff1a;攻击流量模拟真实用户行为&#xff0c;差异率低至0.5%&#xff0c;传统规则引…...

PydanticAI快速入门示例

参考链接&#xff1a;https://ai.pydantic.dev/#why-use-pydanticai 示例代码 from pydantic_ai import Agent from pydantic_ai.models.openai import OpenAIModel from pydantic_ai.providers.openai import OpenAIProvider# 配置使用阿里云通义千问模型 model OpenAIMode…...

ZYNQ学习记录FPGA(二)Verilog语言

一、Verilog简介 1.1 HDL&#xff08;Hardware Description language&#xff09; 在解释HDL之前&#xff0c;先来了解一下数字系统设计的流程&#xff1a;逻辑设计 -> 电路实现 -> 系统验证。 逻辑设计又称前端&#xff0c;在这个过程中就需要用到HDL&#xff0c;正文…...

第22节 Node.js JXcore 打包

Node.js是一个开放源代码、跨平台的、用于服务器端和网络应用的运行环境。 JXcore是一个支持多线程的 Node.js 发行版本&#xff0c;基本不需要对你现有的代码做任何改动就可以直接线程安全地以多线程运行。 本文主要介绍JXcore的打包功能。 JXcore 安装 下载JXcore安装包&a…...