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

数据结构 -- 图的存储

news 来源：原创 2025/9/6 3:52:57

图的存储

邻接矩阵法

邻接矩阵存储不带权图

0 - 表示两个顶点不邻接

1 - 表示两个顶点邻接

在无向图中，每条边在矩阵中对应两个1

在有向图中，每条边在矩阵中对应一个1

//不带权图的邻接矩阵存储
#define MaxVertexNum 100		//顶点数目的最大值
typedef struct{char Vex[MaxVertexNum];int Edge[MaxVertexNum][MaxVertexNum];		//邻接矩阵，边表int vexnum,arcnum;			//图当前顶点数和边数/弧数
}MGraph;

因为矩阵中只需要存放0和1，所以也可以将Edge（二维数组）定义为bool类型或枚举类型，让矩阵变得更小，节省存储空间

求顶点的度、入度、出度

无向图：第i个顶点的度 = 第i行（或第i列）的非零元素个数时间复杂度O(|V|)

有向图：第i个顶点的入度 = 第i行的非零元素个数时间复杂度O(|V|)

第i个顶点的出度 = 第i列的非零元素个数时间复杂度O(|V|)

第i个顶点的度 = 第i行和第i列的非零元素个数之和时间复杂度O(|V|)

邻接矩阵存储带权图（网）

//邻接矩阵存储带权图（网）
#define MaxVertexNum 100		//顶点数目的最大值
#define INFINITY 最大的int值	//宏定义常量“无穷”		使用int的上限值表示“无穷”
typedef char VertexType;		//顶点的数据类型
typedef int EdgeType;			//带权图中边上权值的数据类型
typedef struct{VertexType Vex[MaxVertexNum];			//顶点EdgeType Edge[MaxVertexNum][MaxVertexNum];		//边的权int vexnum,arcnum;			//图的当前定点数和弧数
}

若两个顶点间没有边，则权值为无穷

也有一些教材将一个顶点与自身的权值记作0，所以在使用邻接矩阵表示带权图（网）时，如果两个点之间权值为0或∞，则代表这两个顶点间没有边

邻接矩阵法的性能分析

空间复杂度：O(|V|²) – 只和顶点数相关，和实际边数无关

当边数较少时，有大量的空间被浪费，所以邻接矩阵法适用于存储稠密图

无向图的邻接矩阵是对称矩阵，可以进行压缩存储（只存储上三角区/下三角区）

邻接矩阵的性质

设图G的邻接矩阵为A（矩阵元素为0/1），则Aⁿ的元素Aⁿ[i][j]等于由顶点i到顶点j的长度为n的路径的数目

邻接表法（顺序+链式存储）

//用邻接表存储的图
typedef struct{AdjList vertices;int vexnum,arcnum;
}ALGraph;
//顶点
typedef struct VNode{VertexType data;	//顶点信息ArcNode *first;		//第一条边/弧    
}VNode,AdjList[MaxVertexNum];
//“边/弧”
typedef struct ArcNode{int adjvex;		//边/弧指向哪个结点struct ArcNode *next;		//指向下一条弧的指针//InfoType info			//边权值
}ArcNode;//与树的孩子表示法相同

空间复杂度

无向图：边结点的数量为2|E|，整体的空间复杂度为O(|V|+2|E|)

有向图：边结点的数量为|E|，整体的空间复杂度为O(|V|+|E|)

求顶点的度、入度、出度

无向图：度 = 顶点指向的边链表中结点的数量

有向图：度 = 入度 + 出度

出度 = 顶点指向的边链表中结点的数量

入度 = 指向当前结点的弧的数量（需要遍历所有结点的边链表）

同一个图的邻接表表示方式不唯一（边链表各结点的顺序是任意的）

邻接表和邻接矩阵

	邻接表	邻接矩阵
空间复杂度	无向图：O(\|V\|+2\|E\|)；有向图：O(\|V\|+\|E\|)	O(\|V\|²)
适用于	存储稀疏图	存储稠密图
表示方式	不唯一	唯一
计算度/入度/出度	计算有向图的度和入度不方便，其余很方便	必须遍历对应的行和列
找相邻的边	找有向图的入边不方便，其余很方便	必须遍历对应的行和列

十字链表法、邻接多重表

十字链表法（存储有向图）

【有向图存储】

邻接表：入度、入边寻找计算不方便

邻接矩阵：空间复杂度高

在这里插入图片描述

空间复杂度：O(|V|+|E|)

找出边：顺着绿色线路找

找入边：顺着橙色路线找

注意：十字链表法只能用于存储有向图

邻接多重表（存储无向图）

【存储无向图】

邻接表：每条边对应两份冗余信息，删除顶点、删除边时间复杂度高

邻接矩阵：空间复杂度高

在这里插入图片描述

空间复杂度：O(|V|+|E|)

删除边、删除节点等操作很方便

注意：邻接多重表只适用于存储无向图

小结

	邻接表	邻接矩阵	十字链表法	邻接多重表
空间复杂度	无向图：O(\|V\|+2\|E\|)；有向图：O(\|V\|+\|E\|)	O(\|V\|²)	O(\|V\|+\|E\|)	O(\|V\|+\|E\|)
适用于	存储稀疏图	存储稠密图	只能存有向图	只能存无向图
表示方式	不唯一	唯一	不唯一	不唯一
删除边或顶点	无向图中删除边或删除顶点都不方便	删除边很方便，删除顶点需要大量移动数据	很方便	很方便
找相邻的边	找有向图的入边必须遍历整个邻接表	遍历对应行或列，时间复杂度O(\|V\|)	很方便	很方便

数据结构 -- 图的存储

图的存储邻接矩阵法邻接矩阵存储不带权图 0 - 表示两个顶点不邻接 1 - 表示两个顶点邻接在无向图中，每条边在矩阵中对应两个1 在有向图中，每条边在矩阵中对应一个1 //不带权图的邻接矩阵存储 #define MaxVertexNum 100 //顶点数目的最大值 typed…...

编程日记 2025/9/6 3:52:57

基于大模型预测不稳定性心绞痛的多维度研究与应用

目录一、引言 1.1 研究背景与意义 1.2 研究目的 1.3 国内外研究现状二、不稳定性心绞痛概述 2.1 定义与分类 2.2 发病机制 2.3 临床表现三、大模型技术原理与应用基础 3.1 大模型介绍 3.2 在医疗领域的应用现状 3.3 用于不稳定性心绞痛预测的可行性四、术前预…...

编程日记 2025/9/2 17:39:24

【Java集合】LinkedList源码深度分析

参考笔记：java LinkedList 源码分析（通俗易懂)_linkedlist源码分析-CSDN博客目录 1.前言 2.LinkedList简介 3.LinkedList的底层实现 4.LinkedList 与 ArrayList 的对比 4.1 如何选择 4.2 对比图 5.LinkedList 源码Debug 5.1 add(E e) &#xff…...

编程日记 2025/9/3 0:21:23

Java 大视界 -- Java 大数据在智能供应链库存优化与成本控制中的应用策略（172）

💖亲爱的朋友们，热烈欢迎来到青云交的博客！能与诸位在此相逢，我倍感荣幸。在这飞速更迭的时代，我们都渴望一方心灵净土，而我的博客正是这样温暖的所在。这里为你呈上趣味与实用兼具的知识，也…...

编程日记 2025/9/5 10:22:22

高并发系统架构设计核心要点的结构化提炼【大模型总结】

以下是对高并发系统架构设计核心要点的结构化提炼，结合技术深度与实践视角，以清晰的层次呈现关键策略与实现路径： 一、核心理念重塑 1. 容错优先思维设计哲学：从"零故障"转向"可恢复性"设计，接…...

编程日记 2025/9/3 7:33:42

【C#深度学习之路】如何使用C#实现Stable Diffusion的文生图功能

【C#深度学习之路】如何使用C#实现Stable Diffusion的文生图功能项目背景项目实现写在最后项目下载链接本文为原创文章，若需要转载，请注明出处。原文地址：https://blog.csdn.net/qq_30270773/article/details/147002073 项目对应的Github地…...

编程日记 2025/9/3 10:38:02

k8s的pod的概述和配置

概念 Pod 容器组是一个k8s中一个抽象的概念，用于存放一组 container（可包含一个或多个 container 容器，即图上正方体)，以及这些 container （容器）的一些共享资源。这些资源包括： 共享存储&…...

编程日记 2025/9/3 10:37:57

RTOS任务句柄的作用

任务句柄（Task Handle）在 FreeRTOS 中的作用详解任务句柄（TaskHandle_t）是 FreeRTOS 中用于唯一标识和管理任务的核心机制，本质是一个指向任务控制块（TCB）的指针。说明即便创建的任务名相同，但对应的任务句柄一定是不同。它在任务管理、通信、调试中起到关键作用，…...

编程日记 2025/9/5 10:41:11

OpenVLA-OFT——微调VLA的三大关键设计：并行解码、动作分块、连续动作表示以及L1回归目标

前言 25年3.26日，这是一个值得纪念的日子，这一天，我司「七月在线」的定位正式升级为了：具身智能的场景落地与定制开发商 ，后续则从定制开发逐步过渡到标准产品化比如25年q2起，在定制开发之外&#xff0…...

编程日记 2025/9/4 13:04:16

LocaDate、LocalTime、LocalDateTime

Java8的时间处理 Java的时间处理在早期版本中存在诸多问题（如 java.util.Date 和 java.util.Calendar 的混乱设计），但Java8引入了引入了全新的 java.time包（基于JSR 310），提供了更清晰、线程安全且强大的时…...

编程日记 2025/9/3 10:37:45

哈密尔顿路径（Hamiltonian Path）及相关算法题目

哈密尔顿路径要求访问图中每个顶点恰好一次，通常用于解决旅行商问题（TSP）或状态压缩DP问题。哈密尔顿路径（Hamiltonian Path）是指在一个图中经过每个顶点恰好一次的路径。如果这条路径的起点和终点相同（即…...

编程日记 2025/9/5 4:27:36

突破传统限制！全新端到端开放词汇多目标跟踪框架OVTR，开启视觉追踪新纪元

在自动驾驶和智能监控等场景中，多目标跟踪（MOT）技术需要应对现实世界中层出不穷的新物体类别。传统方法依赖预定义类别，面对“无人机配件”“新型宠物”等未知目标时往往失效。上海人工智能实验室团队提出的OVTR（Open-…...

编程日记 2025/9/5 13:43:57

Springboot + Vue + WebSocket + Notification实现消息推送功能

实现功能基于Springboot与Vue架构，首先使用Websocket实现频道订阅，在实现点对点与群发功能后，在前端调用windows自带的消息通知，实现推送功能。开发环境 Springboot 2.6.7vue 2.6.11socket-client 1.0.0 准备工作在 Vue.js…...

编程日记 2025/9/3 10:37:33

Linux内核物理内存组织结构

一、系统调用sys_mmap 系统调用mmap用来创建内存映射，把创建内存映射主要的工作委托给do_mmap函数，内核源码文件处理：mm/mmap.c 二、系统调用sys_munmap 1、vma find_vma (mm, start); // 根据起始地址找到要删除的第一个虚拟内存区域 vma 2…...

编程日记 2025/9/6 3:52:57

Redis高级技能进阶

什么是事务的ACID 事务是由一系列对系统中数据进行访问或更新的操作组成的程序执行逻辑单元。这些操作要么都执行，要么都不执行。为了保证数据库的一致性，在事务处理之前和之后，都应该遵循某些规则，也就是大家耳熟能详的ACID。 …...

编程日记 2025/9/3 10:37:25

PCB设计基础：面向嵌入式工程师的系统性指南

嵌入式系统的性能、稳定性和可靠性，很大程度上依赖于电路硬件的设计质量。在硬件设计中，PCB（Printed Circuit Board）设计是连接系统功能与实际运行的关键一环。本文将从嵌入式工程师的视角，系统性地介绍PCB设计的关键基…...

编程日记 2025/9/6 3:52:57

aspark 配置2

编写Hadoop集群启停脚本 1.建立新文件，编写脚本程序在hadoop101中操作，在/root/bin下新建文件：myhadoop，输入如下内容： 2.分发执行权限保存后退出，然后赋予脚本执行权限 [roothadoop101 ~]$ chmod x /r…...

编程日记 2025/9/5 7:06:59

【统计方法】LASSO筛变量

启比较原始做LASSO包是library(glmnet) 若目标是纯 LASSO 分析，alpha 必须设为 1 标准化数据：LASSO 对特征的尺度敏感，需对数据进行标准化（均值为0，方差为1）。 cv.glmnet获得的lambda.m…...

编程日记 2025/9/5 22:00:22

拥抱健康生活，书写养生新篇

在快节奏的现代生活中，健康愈发成为人们关注的焦点。践行健康养生，并非是一种选择，而是我们对自己和家人应尽的责任。掌握正确的养生之道，不仅能提升生活品质，更能让生命焕发出新的活力。合理饮食是健康的基石。一…...

编程日记 2025/9/3 7:13:54

Shiro学习（五）：Shiro对权限的缓存

一、问题描述由前边的学习中了解，用户的角色权限一般存储在数据库中，每次进行权限校验时都要从数据库查询用户的角色权限信息；对数据库来说这样频繁的查询压力太大了，也影响程序的性能。 Shiro 中执行权限角色校验时&#xff0…...

编程日记 2025/9/3 10:37:05

QGIS实战系列（六）：进阶应用篇——Python 脚本自动化与三维可视化

欢迎来到“QGIS实战系列”的第六期！在前几期中，我们从基础操作到插件应用逐步提升了 QGIS 技能。这一篇，我们将迈入进阶领域，探索如何用 Python 脚本实现自动化，以及如何创建三维可视化效果，让你的 GIS 项目更高效、更立体。第一步：Python 脚本自动化 QGIS 内置了 Py…...

编程日记 2025/9/3 10:37:00

redis-cpp-cpp如何使用lua脚本

1.前言我今天要在项目中使用lua脚本，结果搞半天都没有弄明白这个函数怎么调用，而且也似乎很少有redis相关的博客介绍，ai也回答的不准确！ 2.正文今天用一个例子演示一下下面是lua脚本 const std::string LuaScript R"…...

编程日记 2025/9/3 10:36:56

承接上一个教程，利用委托事件来进行值传递声明变量 public static double plx, ply,plxx,plyy;声明委托、事件 //声明委托 //事件 public delegate void transferDistance(double dis); public static transferDistance doTransfer; 直接读取form1中的变量 publ…...

编程日记 2025/9/3 10:36:52

PyTorch 深度学习 || 6. Transformer | Ch6.1 注意力机制

...

编程日记 2025/9/4 15:08:57

JWT 秘钥的作用机制

JWT 秘钥的作用并不是给前端使用的，而是用于后端服务器内部的一个重要安全机制。 JWT 秘钥的作用签名与验证： 秘钥主要用于对 JWT（JSON Web Token）进行签名和验证后端使用这个秘钥对令牌进行签名，确保令牌的完整性…...

编程日记 2025/9/3 21:18:09

sun.misc.BASE64Encoder 和 sun.misc.BASE64Decoder包

1. 在将别人的项目导入eclipse之后,出现了"sun.misc.BASE64Encoder找不到jar"的错误，我解决的办法是：右键项目》属性》Java Build Path》jre System Library 》access rules 》resolution选择accessible,下面填上**点击确定即可&#xff0…...

编程日记 2025/9/5 18:07:21

Java面试黄金宝典34

1. 主键索引底层的实现原理定义主键索引是数据库中用于唯一标识表中每一行记录的索引，常见的底层实现是 B 树结构。B 树是一种平衡的多路搜索树，由内部节点和叶子节点组成。内部节点只存储索引键和指向下一层节点的指针，不存储实际数据&am…...

编程日记 2025/9/4 15:08:46

计算机系统---CPU

定义与功能中央处理器（Central Processing Unit，CPU），是电子计算机的主要设备之一，是计算机的核心部件。CPU是计算机的运算核心和控制核心，负责执行计算机程序中的指令，进行算术运算、逻辑运算…...

编程日记 2025/9/4 10:10:00

AWS云安全基线：构建企业级安全防护体系的完整指南

1. 引言随着越来越多的企业将其业务和数据迁移到云端,云安全已成为一个不容忽视的关键议题。AWS作为全球领先的云服务提供商,提供了丰富的安全工具和最佳实践。本文将深入探讨如何构建一个全面的AWS云安全基线,以确保您的企业在云环境中的安全性。 2. AWS共享责任模型在深…...

编程日记 2025/9/4 11:24:08

（三十三）Dart 中使用 Pub 包管理系统与 HTTP 请求教程

Dart 中使用 Pub 包管理系统与 HTTP 请求教程 Pub 包管理系统简介 Pub 是 Dart 和 Flutter 的包管理系统，用于管理项目的依赖。通过 Pub，开发者可以轻松地添加、更新和管理第三方库。使用 Pub 包管理系统 1. 找到需要的库访问以下网址&#xff0c…...

编程日记 2025/9/4 15:08:36

如何实现单例模式？

一、模式定义与核心价值单例模式（Singleton Pattern）是一种创建型设计模式，保证一个类仅有一个实例，并提供全局访问点。其核心价值在于： 资源控制：避免重复创建消耗性资源（如数据库连…...

编程日记 2025/9/4 0:21:15

【51单片机】2-4【I/O口】震动传感器控制继电器

1.硬件 51最小系统继电器模块震动传感器模块 2.软件 #include "reg52.h"sbit vibrate P3^3;//震动传感器DO接到P3.3口 sbit switcher P1^1;//继电器控制端IN接到P1.1void Delay2000ms() //11.0592MHz {unsigned char i, j, k;// _nop_();i 15;j 2;k 235;do{…...

编程日记 2025/9/4 15:08:27

正点原子迷你 miniSTM32用ST link烧录后程序不运行（已解决）

情况，在程序和配置都没有问题时检查烧录使用ST linkv2 烧录后有时程序可行，有时不可行解决方法加USB供电配合SW烧录建议直接用USB转串口烧录不推荐JLINK供电，也不推荐ST linkv2供电...

编程日记 2025/9/4 15:08:22

如何确保MQ消息队列不丢失：Java实现与流程分析

前言在分布式系统中，消息队列（Message Queue, MQ）是核心组件之一，用于解耦系统、异步处理和削峰填谷。然而，消息的可靠性传递是使用MQ时需要重点考虑的问题。如果消息在传输过程中丢失，可能会导致数据不一…...

编程日记 2025/9/4 15:08:18

Pascal语言的系统监控

Pascal语言的系统监控引言在现代计算机系统中，系统监控是确保计算机平稳运行的重要组成部分。无论是个人计算机还是大型服务器，监控系统的性能、资源使用及状态，都是提高系统效率、及时发现问题的关键。Pascal语言作为一种结构化编程语言…...

编程日记 2025/9/4 15:08:13

6.0 使用Qt+ OpenCV+Python加载图片

本例作为python图像处理的入门课程1，使用Qt+ OpenCV+Python加载图片。主要有如下几个地方需要注意： 1. OpenCV 默认使用 BGR 格式，而 Qt 使用 RGB。显示前需要转换：cv2.cvtColor(img, cv2.COLOR_BGR2RGB),一般使用某个QLabel控件进行显示。 pic = cv2.cvtColor(pic, cv2.C…...

编程日记 2025/9/4 15:08:09

低成本训练垂直领域文娱大模型的技术路径

标题:低成本训练垂直领域文娱大模型的技术路径内容:1.摘要在文娱产业快速发展且对智能化需求日益增长的背景下，为降低垂直领域文娱大模型的训练成本，本研究旨在探索低成本训练的有效技术路径。采用对现有开源模型进行微调、利用轻量化模型架构以及优化…...

编程日记 2025/9/5 19:54:38

音视频入门基础：RTP专题（21）——使用Wireshark分析海康网络摄像机RTSP的RTP流

一、引言使用vlc等播放器可以播放海康网络摄像机的RTSP流： 网络摄像机的RTSP流中，RTSP主要用于控制媒体流的传输，如播放、暂停、停止等操作。RTSP本身并不用于转送媒体流数据，而是会通过PLAY方法使用RTP来传输实际的音视频数据。…...

编程日记 2025/9/4 15:08:02

【Java网络编程详解】

文章目录前言一、网络编程基础知识1. 什么是网络编程？ 二、Java网络编程核心类三、TCP编程实现1. TCP通信原理2. TCP服务器端示例3. TCP客户端示例四、UDP编程实现1. UDP通信原理2. UDP服务器端示例3. UDP客户端示例五、使用HttpURLConnection发送HTTP请求1. GET…...

编程日记 2025/9/4 6:16:33

DuckDB系列教程：如何分析Parquet文件

Parquet 是一种强大的、基于列的存储格式，适用于实现更快捷和更高效的数据分析。您可以使用 DuckDB 这种内存型分析数据库来处理 Parquet 文件并运行查询以对其进行分析。在这篇文章中，我们将逐步介绍如何使用 DuckDB 对存储在 Parquet 文件中的餐厅订单…...

编程日记 2025/9/5 19:32:34

uniapp的v-for不显示或者swiper-item的不显示

今天开发的时候碰见一个问题，在布局的时候发现v-for遍历的时候不显示内容 H5是正常的但是在小程序就是不显示最后排查的原因是同一个组件 swiper-item的 v-for不能用相同的名称比如 <swiper-item v-for"i in 3" :key"i"><image …...

编程日记 2025/9/4 15:07:52

解决LeetCode“使括号有效的最少添加”问题

目录问题描述解题思路复杂度分析示例分析暴力替换“不讲码德” 总结问题描述给定一个仅由 ( 和 ) 组成的字符串 s，我们需要通过添加最少数量的括号（( 或 )）使得字符串有效。有效字符串需满足： 空字符串是有效的。 …...

编程日记 2025/9/5 19:58:45

黑马点评_知识点

将手机验证码保存到HttpSession中进行验证（感觉已经过时） Controller中的参数有HttpSession，存验证码session.setAttribute(SystemConstants.VERIFY_CODE, code); 其他的都是逻辑代码 Cookie的缺点什么是Session集群共享问题？ …...

编程日记 2025/9/6 1:04:16

2025年渗透测试面试题总结-某腾讯-玄武实验室扩展（题目+回答）

网络安全领域各种资源，学习文档，以及工具分享、前沿信息分享、POC、EXP分享。不定期分享各种好玩的项目及好用的工具，欢迎关注。目录某腾讯-玄武实验室扩展一、Web安全基础原理与关联漏洞 1.1 CSRF攻击原理深度解析 1.2 反序列化漏洞…...

编程日记 2025/9/4 15:07:40

管理系统 UI 设计：提升企业办公效率的关键

一、管理系统UI设计的基本原则管理系统UI设计应遵循一系列基本原则，以确保界面友好、操作便捷、信息直观。这些原则包括： 简洁性：界面应去除冗余元素，保持简洁明了，避免用户迷失在复杂界面中。一致性：界…...

编程日记 2025/9/4 15:07:37

Apache Commons Lang3 中的 `isNotEmpty` 与 `isNotBlank`的区别

前言在 Java 开发中，字符串的空值（null）、空字符串（“”）和空白字符串（如 " "）的判断是高频需求。Apache Commons Lang3 的 StringUtils 类提供了两个核心方法：isNotEmp…...

编程日记 2025/9/4 15:07:33

WPF 登录页面

效果项目结构 LoginWindow.xaml <Window x:Class"PrismWpfApp.Views.LoginWindow"xmlns"http://schemas.microsoft.com/winfx/2006/xaml/presentation"xmlns:x"http://schemas.microsoft.com/winfx/2006/xaml"xmlns:d"http://schemas.…...

编程日记 2025/9/4 15:07:29