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

【数据结构与算法】图的存储(邻接矩阵,邻接表)详解

图的邻接矩阵数据结构

typedef enum { NDG, DG, NDN, DN } GraphKind;using VRType = int;
using InfoType = int;typedef struct ArcCell {VRType adj;InfoType *info;
} Arc[N][N];struct MGraph {ElemType vexs[N];Arc arc;int vexnum, arcnum;GraphKind kind;
};

ArcCell 结构体包含两个成员:

  • adj 是一个 VRType 类型的变量,表示顶点之间的关系,例如,如果两个顶点之间存在边,那么 adj 表示这条边的权重。
  • info 是一个指向 InfoType 类型的指针,用于存储与边相关的额外信息。

MGraph 结构体包含四个成员:

  • vexs 是一个 ElemType 类型的数组,用于存储图的顶点。
  • arc 是一个 Arc 类型的二维数组,用于存储图的边。
  • vexnum 是一个整数,表示图的顶点数量。
  • arcnum 是一个整数,表示图的边数量。
  • kind 是一个 GraphKind 类型的枚举,表示图的类型。

图的数组表示法、邻接表存贮结构各自的优缺点,适应的运算。

  1. 图的数组表示法(邻接矩阵):

    • 优点:容易实现图的操作,如:求某顶点的度、判断顶点之间是否有边(弧)、找顶点的邻接点等等。
    • 缺点:n个顶点需要n*n个单元存储边(弧);空间效率为 O ( n 2 ) O(n^2) O(n2)。 对稀疏图而言尤其浪费空间。
    • 适应的运算:边的数量较多,需要频繁检查节点间是否存在边的场景。
  2. 图的邻接表存储结构:

    • 优点:n个顶点、e条边的无向图,只需要n个头结点和2e个表结点。对稀疏图而言,比数组表示法节省存储空间。
    • 缺点:每条边需要对应两个表结点。
    • 适应的运算:边的数量较少,需要频繁添加或删除边的场景。

相关文章:

【数据结构与算法】图的存储(邻接矩阵,邻接表)详解

图的邻接矩阵数据结构 typedef enum { NDG, DG, NDN, DN } GraphKind;using VRType int; using InfoType int;typedef struct ArcCell {VRType adj;InfoType *info; } Arc[N][N];struct MGraph {ElemType vexs[N];Arc arc;int vexnum, arcnum;GraphKind kind; };ArcCell 结构…...

【深度C++】之“类与结构体”

0. 抽象数据类型 类(class) 和结构体(struct) 都是C中的自定义数据类型,是使用C实现面向对象编程思想的起点。 类的基本思想是数据抽象(data abstraction) 和封装(encapsulation&a…...

CTO的职责是什么?

看《架构思维》作者是这样讲的: CTO 到底是做什么的? 我当下的答案是:“CTO 就是一个从技术视角出发,为公司或者所在的部门做正确决策的 CEO。”怎么理解这句话呢?作为一个 CTO,其长期目标和决策优先级与…...

【GD32】从零开始学兆易创新32位微处理器——RTC实时时钟+日历例程

1 简介 RTC实时时钟顾名思义作用和墙上挂的时钟差不多,都是用于记录时间和日历,同时也有闹钟的功能。从硬件实现上来说,其实它就是一个特殊的计时器,它内部有一个32位的寄存器用于计时。RTC在低功耗应用中可以说相当重要&#xf…...

HTTP网络协议

1.HTTP (1)概念: Hyper Text Transfer Protocol,超文本传输协议规定了浏览器和服务器之间数据传输的规则。 (2)特点 基于TCP协议:面向连接,安全基于请求-响应模型的:一次请求对应一次响应HTTP协…...

Kubernetes相关生态

1、Prometheus、Metrics Server与Kubernetes监控体系 简介: Prometheus 项目与 Kubernetes 项目一样,也来自于 Google 的 Borg 体系,它的原型系统,叫作 BorgMon,是一个几乎与 Borg 同时诞生的内部监控系统 Pro…...

C语言入门4-函数和程序结构

函数举例 读取字符串&#xff0c;如果字符串中含有ould则输出该字符串&#xff0c;否则不输出。 #include <stdio.h>// 函数声明 int getLine(char s[], int lim); int strindex(char s[], char t[]);int main() {char t[] "ould"; // 要查找的目标子字符串…...

分行业二氧化碳排放数据

分行业二氧化碳排放量 资源名称&#xff1a;分行业二氧化碳排放量 数据来源&#xff1a;中国能源统计年鉴 时间范围&#xff1a;1995-2018年指标&#xff1a;八类能源和总量&#xff1a;煤炭、焦炭、原油、汽油、煤油、柴油、燃料油、天然气...

【OS基础】符合AUTOSAR标准的RTAOS-Alarms详解

目录 前言 正文 7.报警Alarms 7.1配置Alarms 7.1.1激活一个任务 7.1.2 设置一个事件 7.1.3报警回调Alarm Callback 7.1.4 增加计数器值 7.2设置Alarms 7.2.1 绝对Alarms 7.2.2 相对Alarm 7.3自启动Alarms 7.4 删除Alarms 7.5确认何时会发生Alarm 7.6非周期Alarm…...

基于Java的学生成绩管理系统

你好呀&#xff0c;我是计算机学姐码农小野&#xff01;如果有相关需求&#xff0c;可以私信联系我。 开发语言&#xff1a;Java 数据库&#xff1a;MySQL 技术&#xff1a;Java技术&#xff0c;B/S结构 工具&#xff1a;MyEclipse&#xff0c;MySQL 系统展示 首页 个人中…...

都2024年了,还有人不懂动态代理么?

文章目录 一、定义二、静态代理三、动态代理1. JDK代理1.1 JDK代理实现流程1.2 动态生成的类字节码 2. Cglib代理2.1 Cglib实现流程 四、总结 一、定义 静态代理和动态代理都反映了一个代理模式&#xff0c;代理模式是一种经典的设计模式&#xff0c;常用于为其他对象提供一种…...

ARM功耗管理框架之PPU

安全之安全(security)博客目录导读 思考&#xff1a;功耗管理框架&#xff1f;SCP&#xff1f;PPU&#xff1f;LPI&#xff1f;之间的关系&#xff1f;如何配合&#xff1f; 目录 一、功耗管理框架中的PPU 二、PPU的结构与连接关系 三、PPU操作模式和电源模式及其之间的转…...

说说 SSL 的错误认识和不足之处

最近明月在学习折腾 LNMP 期间无意中建了一个 Typecho 的博客小站&#xff0c;近一周的折腾下来&#xff0c;收获真的不少&#xff0c;致使兴趣也越来越浓了&#xff0c;在升级 LNMP 的时候捎带手的给这个 Typecho 博客也启用了 SSL。并且开启了 memcached 和 OPcache 优化加速…...

Go语言day1

下载go语言的安装程序&#xff1a; All releases - The Go Programming Language 配置go语言的环境变量&#xff1a; 写第一个go语言 在E:\go_workspace当前窗口使用cmd命令: 输入 go run test.go...

【Python机器学习】利用t-SNE进行流形学习

虽然PCA通常是用于变换数据的首选方法&#xff0c;使你能够用散点图将其可视化&#xff0c;但这一方法的性质限制了其有效性。 有一类用于可视化的算法叫做流形学习算法&#xff0c;它允许进行更复杂的映射&#xff0c;通常也可以给出更好的可视化。其中特别有用的一个就是t-S…...

03 - matlab m_map地学绘图工具基础函数 - 设置坐标系(m_coord)

03 - matlab m_map地学绘图工具基础函数 - 设置坐标系&#xff08;m_coord&#xff09; 0. 引言1. m_proj使用方法2. 结语 0. 引言 上一篇介绍了m_proj函数用于初始化投影&#xff0c;本篇介绍的函数m_coord用于初始化地理坐标系或地磁坐标系&#xff0c;地理/地磁坐标系和投影…...

UEC++ 虚幻5第三人称射击游戏(一)

UEC 虚幻5第三人称射击游戏&#xff08;一&#xff09; 创建一个空白的C工程 人物角色基本移动 创建一个Character类添加一些虚幻商城中的基础动画 给角色类添加Camera与SPringArm组件 UPROPERTY(VisibleAnywhere, BlueprintReadOnly, Category "SpringArm")clas…...

java小代码(1)

代码 &#xff1a; 今日总结到此结束&#xff0c;拜拜&#xff01;...

SLAM ORB-SLAM2(27)词袋模型

SLAM ORB-SLAM2(27)词袋模型 1. 词袋模型1.1. 词汇树1.2. 逆向索引表1.3. 逆向索引表2. 词袋向量3. 匹配候选帧3.1. 找出和当前帧具有公共单词的所有关键帧3.2. 找出和当前帧最多公共单词的关键帧3.3. 剔除共享单词数较少的关键帧3.4. 计算关键帧的共视关键帧组的总得分3.5. …...

OpenAI 的 GPT-5:CTO米拉-穆拉提说,到 2026 年将实现博士级智能(Ph.D.-Level))

据首席技术官米拉-穆拉提&#xff08;Mira Murati&#xff09;介绍&#xff0c;GPT-5 是 OpenAI 人工智能的下一代进化产品&#xff0c;将于 2025 年底或 2026 年初在特定任务中实现博士级智能。 GPT-5 内部代号为 "Gobi "和 “Arrakis”&#xff0c;将是一个多模态…...

synchronized 学习

学习源&#xff1a; https://www.bilibili.com/video/BV1aJ411V763?spm_id_from333.788.videopod.episodes&vd_source32e1c41a9370911ab06d12fbc36c4ebc 1.应用场景 不超卖&#xff0c;也要考虑性能问题&#xff08;场景&#xff09; 2.常见面试问题&#xff1a; sync出…...

智慧医疗能源事业线深度画像分析(上)

引言 医疗行业作为现代社会的关键基础设施,其能源消耗与环境影响正日益受到关注。随着全球"双碳"目标的推进和可持续发展理念的深入,智慧医疗能源事业线应运而生,致力于通过创新技术与管理方案,重构医疗领域的能源使用模式。这一事业线融合了能源管理、可持续发…...

【WiFi帧结构】

文章目录 帧结构MAC头部管理帧 帧结构 Wi-Fi的帧分为三部分组成&#xff1a;MAC头部frame bodyFCS&#xff0c;其中MAC是固定格式的&#xff0c;frame body是可变长度。 MAC头部有frame control&#xff0c;duration&#xff0c;address1&#xff0c;address2&#xff0c;addre…...

2025年能源电力系统与流体力学国际会议 (EPSFD 2025)

2025年能源电力系统与流体力学国际会议&#xff08;EPSFD 2025&#xff09;将于本年度在美丽的杭州盛大召开。作为全球能源、电力系统以及流体力学领域的顶级盛会&#xff0c;EPSFD 2025旨在为来自世界各地的科学家、工程师和研究人员提供一个展示最新研究成果、分享实践经验及…...

PL0语法,分析器实现!

简介 PL/0 是一种简单的编程语言,通常用于教学编译原理。它的语法结构清晰,功能包括常量定义、变量声明、过程(子程序)定义以及基本的控制结构(如条件语句和循环语句)。 PL/0 语法规范 PL/0 是一种教学用的小型编程语言,由 Niklaus Wirth 设计,用于展示编译原理的核…...

Map相关知识

数据结构 二叉树 二叉树&#xff0c;顾名思义&#xff0c;每个节点最多有两个“叉”&#xff0c;也就是两个子节点&#xff0c;分别是左子 节点和右子节点。不过&#xff0c;二叉树并不要求每个节点都有两个子节点&#xff0c;有的节点只 有左子节点&#xff0c;有的节点只有…...

GC1808高性能24位立体声音频ADC芯片解析

1. 芯片概述 GC1808是一款24位立体声音频模数转换器&#xff08;ADC&#xff09;&#xff0c;支持8kHz~96kHz采样率&#xff0c;集成Δ-Σ调制器、数字抗混叠滤波器和高通滤波器&#xff0c;适用于高保真音频采集场景。 2. 核心特性 高精度&#xff1a;24位分辨率&#xff0c…...

视觉slam十四讲实践部分记录——ch2、ch3

ch2 一、使用g++编译.cpp为可执行文件并运行(P30) g++ helloSLAM.cpp ./a.out运行 二、使用cmake编译 mkdir build cd build cmake .. makeCMakeCache.txt 文件仍然指向旧的目录。这表明在源代码目录中可能还存在旧的 CMakeCache.txt 文件,或者在构建过程中仍然引用了旧的路…...

LINUX 69 FTP 客服管理系统 man 5 /etc/vsftpd/vsftpd.conf

FTP 客服管理系统 实现kefu123登录&#xff0c;不允许匿名访问&#xff0c;kefu只能访问/data/kefu目录&#xff0c;不能查看其他目录 创建账号密码 useradd kefu echo 123|passwd -stdin kefu [rootcode caozx26420]# echo 123|passwd --stdin kefu 更改用户 kefu 的密码…...

基于PHP的连锁酒店管理系统

有需要请加文章底部Q哦 可远程调试 基于PHP的连锁酒店管理系统 一 介绍 连锁酒店管理系统基于原生PHP开发&#xff0c;数据库mysql&#xff0c;前端bootstrap。系统角色分为用户和管理员。 技术栈 phpmysqlbootstrapphpstudyvscode 二 功能 用户 1 注册/登录/注销 2 个人中…...