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

【数据结构】图的存储结构及实现(邻接表和十字链表)

一.邻接矩阵的空间复杂度

假设图G有n个顶点e条边,则存储该图需要O(n^2)

不适用稀疏图的存储

二.邻接表

1.邻接表的存储思想:

对于图的每个顶点vi,将所有邻接于vi的顶点链成一个单链表,称为顶点vi的边表(对于有向图则称为出边表),所有边表的头指针和存储顶点信息的一维数组构成了顶点表。

2.邻接表的结构定义

struct ArcNode{int adjvex;struct ArcNode *next;
};template <class T>
struct VertexNode{T vertex;struct ArcNode *firstEdge;
};

邻接表的空间复杂度为O(n+e)

更适用于有向图的存储

3.无向图的邻接表

1.如何求顶点i的度?

顶点i的边表中结点的个数 

2.如何判断顶点vi和vj之间是否有边?

测试顶点vi的边表中是否有终点为j的结点

4.有向图的邻接表

1.如何求顶点i的出度?

顶点i的边表中结点的个数 

2.如何求顶点i的入度?

各顶点的出边表中以顶点i为终点的结点个数

5.网图的邻接表

三.邻接表存储有向图的类

struct ArcNode{int adjvex;struct ArcNode *next;
};template <class T>
struct VertexNode{T vertex;struct ArcNode *firstEdge;
};
template <class T>
class ALGraph{
private:VertexNode<T> adjList[MAX_VERTEX];int vertexNum,arcNum;
public:ALGraph(T v[],int n,int e);~ALGraph();void DFSTraverse();void BFSTraverse();
};

template <class T>
ALGraph<T>::ALGraph(T v[],int n,int e){int vi,vj;ArcNode *s;vertexNum=n;arcNum=e;for(int i=0;i<n;i++){adjList[i].vertex=v[i];adjList[i].firstEdge=NULL;}for(int i=0;i<arcNum;i++){cin>>vi>>vj;s=new ArcNode;s->adjvex=vj;s->next=adjList[vi].firstEdge;adjList[vi].firstEdge=s;}
}
template <class T>
ALGraph<T>::~ALGraph(){int i,j;ArcNode *p;for(i=0;i<vertexNum;i++){p=adjList[i].firstEdge;if(p){while(p){adjList[i].firstEdge=p->next;delete p;p=adjList[i].firstEdge;}}}
}

 

四.逆邻接表

对于邻接表来说,查找入度非常困难。

所以引入了逆邻接表。

五.十字链表 

十字链表的结点结构:

六.图的存储结构的比较

相关文章:

【数据结构】图的存储结构及实现(邻接表和十字链表)

一.邻接矩阵的空间复杂度 假设图G有n个顶点e条边&#xff0c;则存储该图需要O&#xff08;n^2) 不适用稀疏图的存储 二.邻接表 1.邻接表的存储思想&#xff1a; 对于图的每个顶点vi&#xff0c;将所有邻接于vi的顶点链成一个单链表&#xff0c;称为顶点vi的边表&#xff08…...

ROS Turtlebot3多机器人编队导航仿真

文章目录 前言一、Gzazebo中加载多台Turtlebot3机器人二、RVIZ中加载多个Turtlebot3机器人三.多机器人编队导航总结 前言 前面已经实现了在gazebo仿真环境中机器人一字型编队、三角形编队、N字型编队等仿真&#xff0c;接下来考虑多机器人编队在编队行进过程中的避障问题&…...

端口配置错误,导致RabbitMq启动报错

SpringBoot启动&#xff0c;报错如下&#xff1a; 2023-11-19 01:33:43.030 UID[] [] [AMQP Connection 116.xxx.xx.xxx:15672] ERROR com.rabbitmq.client.impl.ForgivingExceptionHandler - An unexpected connection driver error occured java.net.SocketException: Sock…...

<MySQL> 什么是JDBC?如何使用JDBC进行编程?

目录 一、JDBC是什么&#xff1f; 二、JDBC常用接口和类 2.1 DataSource 2.2 Connection 2.3 Statement 2.4 ResultSet 三、JDBC的使用 3.1 获得数据库驱动包 3.2 添加到项目依赖 3.3 描述数据库服务器 3.4 建立数据库连接 3.6 执行SQL语句和接收返回数据 3.7 释放…...

基于安卓android微信小程序的装修家装小程序

项目介绍 巧匠家装小程序的设计主要是对系统所要实现的功能进行详细考虑&#xff0c;确定所要实现的功能后进行界面的设计&#xff0c;在这中间还要考虑如何可以更好的将功能及页面进行很好的结合&#xff0c;方便用户可以很容易明了的找到自己所需要的信息&#xff0c;还有系…...

基于SSM的小区物业管理系统设计与实现

末尾获取源码 开发语言&#xff1a;Java Java开发工具&#xff1a;JDK1.8 后端框架&#xff1a;SSM 前端&#xff1a;Vue 数据库&#xff1a;MySQL5.7和Navicat管理工具结合 服务器&#xff1a;Tomcat8.5 开发软件&#xff1a;IDEA / Eclipse 是否Maven项目&#xff1a;是 目录…...

c语言免杀火绒

文章目录 前记c加载器补充知识 前记 pyinstaller pyinstaller目前已经被杀疯了&#xff0c;简单打包一个hello a"hello" print(a)#pyinstaller -F -w b.py -n HipsMain.exe考虑Nuitka pip uninstall nuitka pip install nuitka pip install nuitka1.8.5 这里最新…...

MyBatis #{} 和 ${} 的区别

前言&#xff1a; #{} 和 ${} 的区别是 MyBatis 中一个常见的面试题&#xff0c;#{} 和 ${} 是MyBatis 中获取参数的两种方式&#xff0c;但我们在项目中大多数使用的都是 #{} 来获取参数&#xff0c;那么它们两个有什么区别呢&#xff1f; 区别 一. #{} 采用预编译 SQL&…...

计算机科学速成课

建议看看计算机科学速成课&#xff0c;一门很全面的计算机原理入门课程&#xff0c;短短10分钟可以把大学老师十几节课讲的东西讲清楚&#xff01;整个系列一共41个视频&#xff0c;B站上有中文字幕版。 每个视频都是一个特定的主题&#xff0c;例如软件工程、人工智能、操作系…...

基于单片机的汽车安全气囊系统故障仿真设计

**单片机设计介绍&#xff0c; 基于单片机微波炉加热箱系统设计 文章目录 一 概要二、功能设计设计思路 三、 软件设计原理图 五、 程序六、 文章目录 一 概要 基于单片机的汽车安全气囊系统的故障检测系统是一种用于检测安全气囊系统故障的智能化设备&#xff0c;通过单片机控…...

JPA整合Sqlite解决Dialect报错问题, 最新版Hibernate6

前言 我个人项目中&#xff0c;不想使用太重的数据库&#xff0c;而内嵌数据库中SQLite又是最受欢迎的&#xff0c; 因此决定采用这个数据库。 可是JPA并不支持Sqlite&#xff0c;这篇文章就是记录如何解决这个问题的。 原因 JPA屏蔽了底层的各个数据库差异&#xff0c; 但是…...

算法通关村第十关-青铜挑战快速排序

大家好我是苏麟,今天带来快速排序 . 快速排序 单边快速排序(lomuto 洛穆托分区方案) 单边循环 (lomuto分区) 要点 : 选择最右侧元素作为基准点j 找比基准点小的&#xff0c;i 找比基准点大的&#xff0c;一旦找到&#xff0c;二者进行交换。 交换时机: 找到小的&#xff0c…...

whisper large-v3 模型文件下载链接

#源码里找到的_MODELS {"tiny.en": "https://openaipublic.azureedge.net/main/whisper/models/d3dd57d32accea0b295c96e26691aa14d8822fac7d9d27d5dc00b4ca2826dd03/tiny.en.pt","tiny": "https://openaipublic.azureedge.net/main/whisp…...

Ajax 之XMLHttpRequest讲解

一直以来都听别人说Ajax,今天终于接触到了。。。。。。。。。。 一.什么是Ajax? 答: AJAX即“Asynchronous Javascript And XML”&#xff08;异步JavaScript和XML&#xff09;&#xff0c;是指一种创建交互式网页应用的网页开发技术。 AJAX 异步 JavaScript和XML&#x…...

小程序里面循环使用ref的话获取不到

文章目录 概要问题案例解决方法 概要 在小程序里面一般循环使用ref的话会获取不到 问题案例 //这个时自己封装的组件&#xff0c;然后循环使用 <jilianXuanzhe huoqu"huoqu" :ref"jilianXuanzhe i"></jilianXuanzhe>//如果这样使用的话获取…...

PY32F002B从压缩包到实现串口printf输出

最近学习使用芯领的PY32F002B开发板&#xff0c;记录学习历程供有同样需求的人参考。 本文主要讲述利用开发板实现printf语句串口输出。 开发环境的初步搭建 官方提供了一个压缩文件&#xff0c;文件名py32f002B_231026.zip&#xff0c; 链接&#xff1a;https://pan.baidu.c…...

音视频项目—基于FFmpeg和SDL的音视频播放器解析(八)

介绍 在本系列&#xff0c;我打算花大篇幅讲解我的 gitee 项目音视频播放器&#xff0c;在这个项目&#xff0c;您可以学到音视频解封装&#xff0c;解码&#xff0c;SDL渲染相关的知识。您对源代码感兴趣的话&#xff0c;请查看基于FFmpeg和SDL的音视频播放器 如果您不理解本…...

CorelDRAW2024最新版本的图形设计软件

CorelDRAW2024是Corel公司推出的最新版本的图形设计软件。CorelDRAW是一款功能强大的矢量图形编辑工具&#xff0c;被广泛用于图形设计、插图、页面布局、照片编辑和网页设计等领域。 1. 新增的设计工具&#xff1a;CorelDRAW 2024引入了一些全新的设计工具&#xff0c;使用户能…...

【作业】操作系统实验一:进程和线程

文章目录 实验内容一、进程的创建1、编辑源程序2、编辑结果3、编译和运行程序4、解释运行结果 二、进程共享1、运行2、解释运行结果 三、进程终止1、运行2、解释运行结果 四、进程同步1、运行2、解释运行结果 五、Linux中子进程映像的重新装入1、运行2、解释运行结果 六、线程1…...

Linux 环境删除Conda

你可以按照以下步骤操作来删除Conda&#xff1a; 首先&#xff0c;停止所有conda环境。在终端中运行以下命令&#xff1a; conda deactivate然后使用以下命令获取conda安装的路径&#xff1a; which conda如果成功安装了conda&#xff0c;该命令输出的路径应该是类似于这样的&a…...

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

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

Xshell远程连接Kali(默认 | 私钥)Note版

前言:xshell远程连接&#xff0c;私钥连接和常规默认连接 任务一 开启ssh服务 service ssh status //查看ssh服务状态 service ssh start //开启ssh服务 update-rc.d ssh enable //开启自启动ssh服务 任务二 修改配置文件 vi /etc/ssh/ssh_config //第一…...

模型参数、模型存储精度、参数与显存

模型参数量衡量单位 M&#xff1a;百万&#xff08;Million&#xff09; B&#xff1a;十亿&#xff08;Billion&#xff09; 1 B 1000 M 1B 1000M 1B1000M 参数存储精度 模型参数是固定的&#xff0c;但是一个参数所表示多少字节不一定&#xff0c;需要看这个参数以什么…...

Mybatis逆向工程,动态创建实体类、条件扩展类、Mapper接口、Mapper.xml映射文件

今天呢&#xff0c;博主的学习进度也是步入了Java Mybatis 框架&#xff0c;目前正在逐步杨帆旗航。 那么接下来就给大家出一期有关 Mybatis 逆向工程的教学&#xff0c;希望能对大家有所帮助&#xff0c;也特别欢迎大家指点不足之处&#xff0c;小生很乐意接受正确的建议&…...

Auto-Coder使用GPT-4o完成:在用TabPFN这个模型构建一个预测未来3天涨跌的分类任务

通过akshare库&#xff0c;获取股票数据&#xff0c;并生成TabPFN这个模型 可以识别、处理的格式&#xff0c;写一个完整的预处理示例&#xff0c;并构建一个预测未来 3 天股价涨跌的分类任务 用TabPFN这个模型构建一个预测未来 3 天股价涨跌的分类任务&#xff0c;进行预测并输…...

《用户共鸣指数(E)驱动品牌大模型种草:如何抢占大模型搜索结果情感高地》

在注意力分散、内容高度同质化的时代&#xff0c;情感连接已成为品牌破圈的关键通道。我们在服务大量品牌客户的过程中发现&#xff0c;消费者对内容的“有感”程度&#xff0c;正日益成为影响品牌传播效率与转化率的核心变量。在生成式AI驱动的内容生成与推荐环境中&#xff0…...

剑指offer20_链表中环的入口节点

链表中环的入口节点 给定一个链表&#xff0c;若其中包含环&#xff0c;则输出环的入口节点。 若其中不包含环&#xff0c;则输出null。 数据范围 节点 val 值取值范围 [ 1 , 1000 ] [1,1000] [1,1000]。 节点 val 值各不相同。 链表长度 [ 0 , 500 ] [0,500] [0,500]。 …...

postgresql|数据库|只读用户的创建和删除(备忘)

CREATE USER read_only WITH PASSWORD 密码 -- 连接到xxx数据库 \c xxx -- 授予对xxx数据库的只读权限 GRANT CONNECT ON DATABASE xxx TO read_only; GRANT USAGE ON SCHEMA public TO read_only; GRANT SELECT ON ALL TABLES IN SCHEMA public TO read_only; GRANT EXECUTE O…...

HBuilderX安装(uni-app和小程序开发)

下载HBuilderX 访问官方网站&#xff1a;https://www.dcloud.io/hbuilderx.html 根据您的操作系统选择合适版本&#xff1a; Windows版&#xff08;推荐下载标准版&#xff09; Windows系统安装步骤 运行安装程序&#xff1a; 双击下载的.exe安装文件 如果出现安全提示&…...

Mac下Android Studio扫描根目录卡死问题记录

环境信息 操作系统: macOS 15.5 (Apple M2芯片)Android Studio版本: Meerkat Feature Drop | 2024.3.2 Patch 1 (Build #AI-243.26053.27.2432.13536105, 2025年5月22日构建) 问题现象 在项目开发过程中&#xff0c;提示一个依赖外部头文件的cpp源文件需要同步&#xff0c;点…...