【数据结构】图的存储结构及实现(邻接表和十字链表)
一.邻接矩阵的空间复杂度
假设图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条边,则存储该图需要O(n^2) 不适用稀疏图的存储 二.邻接表 1.邻接表的存储思想: 对于图的每个顶点vi,将所有邻接于vi的顶点链成一个单链表,称为顶点vi的边表(…...
ROS Turtlebot3多机器人编队导航仿真
文章目录 前言一、Gzazebo中加载多台Turtlebot3机器人二、RVIZ中加载多个Turtlebot3机器人三.多机器人编队导航总结 前言 前面已经实现了在gazebo仿真环境中机器人一字型编队、三角形编队、N字型编队等仿真,接下来考虑多机器人编队在编队行进过程中的避障问题&…...
端口配置错误,导致RabbitMq启动报错
SpringBoot启动,报错如下: 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是什么? 二、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微信小程序的装修家装小程序
项目介绍 巧匠家装小程序的设计主要是对系统所要实现的功能进行详细考虑,确定所要实现的功能后进行界面的设计,在这中间还要考虑如何可以更好的将功能及页面进行很好的结合,方便用户可以很容易明了的找到自己所需要的信息,还有系…...
基于SSM的小区物业管理系统设计与实现
末尾获取源码 开发语言:Java Java开发工具:JDK1.8 后端框架:SSM 前端:Vue 数据库:MySQL5.7和Navicat管理工具结合 服务器:Tomcat8.5 开发软件:IDEA / Eclipse 是否Maven项目:是 目录…...
c语言免杀火绒
文章目录 前记c加载器补充知识 前记 pyinstaller pyinstaller目前已经被杀疯了,简单打包一个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 #{} 和 ${} 的区别
前言: #{} 和 ${} 的区别是 MyBatis 中一个常见的面试题,#{} 和 ${} 是MyBatis 中获取参数的两种方式,但我们在项目中大多数使用的都是 #{} 来获取参数,那么它们两个有什么区别呢? 区别 一. #{} 采用预编译 SQL&…...
计算机科学速成课
建议看看计算机科学速成课,一门很全面的计算机原理入门课程,短短10分钟可以把大学老师十几节课讲的东西讲清楚!整个系列一共41个视频,B站上有中文字幕版。 每个视频都是一个特定的主题,例如软件工程、人工智能、操作系…...
基于单片机的汽车安全气囊系统故障仿真设计
**单片机设计介绍, 基于单片机微波炉加热箱系统设计 文章目录 一 概要二、功能设计设计思路 三、 软件设计原理图 五、 程序六、 文章目录 一 概要 基于单片机的汽车安全气囊系统的故障检测系统是一种用于检测安全气囊系统故障的智能化设备,通过单片机控…...
JPA整合Sqlite解决Dialect报错问题, 最新版Hibernate6
前言 我个人项目中,不想使用太重的数据库,而内嵌数据库中SQLite又是最受欢迎的, 因此决定采用这个数据库。 可是JPA并不支持Sqlite,这篇文章就是记录如何解决这个问题的。 原因 JPA屏蔽了底层的各个数据库差异, 但是…...
算法通关村第十关-青铜挑战快速排序
大家好我是苏麟,今天带来快速排序 . 快速排序 单边快速排序(lomuto 洛穆托分区方案) 单边循环 (lomuto分区) 要点 : 选择最右侧元素作为基准点j 找比基准点小的,i 找比基准点大的,一旦找到,二者进行交换。 交换时机: 找到小的,…...
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”(异步JavaScript和XML),是指一种创建交互式网页应用的网页开发技术。 AJAX 异步 JavaScript和XML&#x…...
小程序里面循环使用ref的话获取不到
文章目录 概要问题案例解决方法 概要 在小程序里面一般循环使用ref的话会获取不到 问题案例 //这个时自己封装的组件,然后循环使用 <jilianXuanzhe huoqu"huoqu" :ref"jilianXuanzhe i"></jilianXuanzhe>//如果这样使用的话获取…...
PY32F002B从压缩包到实现串口printf输出
最近学习使用芯领的PY32F002B开发板,记录学习历程供有同样需求的人参考。 本文主要讲述利用开发板实现printf语句串口输出。 开发环境的初步搭建 官方提供了一个压缩文件,文件名py32f002B_231026.zip, 链接:https://pan.baidu.c…...
音视频项目—基于FFmpeg和SDL的音视频播放器解析(八)
介绍 在本系列,我打算花大篇幅讲解我的 gitee 项目音视频播放器,在这个项目,您可以学到音视频解封装,解码,SDL渲染相关的知识。您对源代码感兴趣的话,请查看基于FFmpeg和SDL的音视频播放器 如果您不理解本…...
CorelDRAW2024最新版本的图形设计软件
CorelDRAW2024是Corel公司推出的最新版本的图形设计软件。CorelDRAW是一款功能强大的矢量图形编辑工具,被广泛用于图形设计、插图、页面布局、照片编辑和网页设计等领域。 1. 新增的设计工具:CorelDRAW 2024引入了一些全新的设计工具,使用户能…...
【作业】操作系统实验一:进程和线程
文章目录 实验内容一、进程的创建1、编辑源程序2、编辑结果3、编译和运行程序4、解释运行结果 二、进程共享1、运行2、解释运行结果 三、进程终止1、运行2、解释运行结果 四、进程同步1、运行2、解释运行结果 五、Linux中子进程映像的重新装入1、运行2、解释运行结果 六、线程1…...
Linux 环境删除Conda
你可以按照以下步骤操作来删除Conda: 首先,停止所有conda环境。在终端中运行以下命令: conda deactivate然后使用以下命令获取conda安装的路径: which conda如果成功安装了conda,该命令输出的路径应该是类似于这样的&a…...
uni-app(1)pages. json和tabBar
第一步 在HBuilderX中新建项目 填写项目名称、确定目录、选择模板、选择Vue版本:3、点击创建 第二步 配置pages.json文件 pages.json是一个非常重要的配置文件,它用于配置小程序的页面路径、窗口表现、导航条样式等信息。 右键点击pages,按…...
window系统vscode 编译wvp前端代码
下载代码 wvp-GB28181-pro: WEB VIDEO PLATFORM是一个基于GB28181-2016标准实现的网络视频平台,负责实现核心信令与设备管理后台部分,支持NAT穿透,支持海康、大华、宇视等品牌的IPC、NVR、DVR接入。支持国标级联,支持rtsp/rtmp等…...
获取虎牙直播源
为了今天得LOL总决赛 然后想着下午看看 但是网页看占用高 就想起来有个直播源 也不复杂看了大概一个小时 没啥问题 进入虎牙页面只有 直接F12 网络 然后 看这个长条 一直在获取 发送 那就选中这个区间 找到都是数字这一条 如果直接访问的话会一直下载 我这都取消了 然后 打开…...
Halcon (2):Halcon基础知识
文章目录 文章专栏视频资源前言Halcon文档案例学习结论 文章专栏 Halcon开发 视频资源 机器视觉之C#联合Halcon 前言 本章我们主要讲解Halcon的基础语法 Halcon文档 按下F1,就可以看到Halcon的文档,不过都是纯英文的 如果不清楚参数如何使用&#x…...
测不准原理
测不准原理 算符的对易关系 commutation relation 测不准原理的矢量推导 Schwarz inequality: 设对易关系: 设一个新态: 投影: 那么有: 代回Schwarz inequality 即可证明:...
微机原理_12
一、单项选择题(本大题共15小题,每小题3分,共45分。在每小题给出的四个备选项中,选出一个正确的答案。〕 十进制正数56的 8位二进制补码是()。 A. 00011001 B. 10100110 C. 10011001 D. 00100110 若栈顶的物理地址为20100H,当执行完指令PUSH…...
设计模式(5)-使用设计模式实现简易版springIoc
自定义简易版springIoc 1 spring使用回顾 自定义spring框架前,先回顾一下spring框架的使用,从而分析spring的核心,并对核心功能进行模拟。 数据访问层。定义UserDao接口及其子实现类 public interface UserDao {public void add(); }public…...
数据结构与集合源码
我是南城余!阿里云开发者平台专家博士证书获得者! 欢迎关注我的博客!一同成长! 一名从事运维开发的worker,记录分享学习。 专注于AI,运维开发,windows Linux 系统领域的分享! 本…...
nodejs+vue面向中小学课堂教学辅助软件系统的设计与实现-微信小程序-安卓-python-PHP-计算机毕业设计
主要功能有,管理员通过后台会对此教学辅助进行审核,管理员在还可以进行首页、个人中心、学生管理、教师管理、班级信息管理、科目名称管理、课程信息管理、教学资料管理、作业信息管理、作业提交管理、作业成绩管理、在线考试管理、试题管理、考试管理、…...
智能配电系统解决方案
智能配电系统解决方案是一种集成了先进技术和智能化功能的配电系统,它能够提高电力系统的效率、可靠性和安全性。力安科技智能配电系统解决方案依托电易云-智慧电力物联网,具体实施的方案如下: 智能化设备和传感器:采用智能化的开…...
Python基础入门---conda 如何管理依赖包以及复制相同环境的
文章目录 创建虚拟环境:创建虚拟环境并指定Python版本:安装依赖包:从环境导出依赖包清单:从依赖包清单创建环境:复制环境:移植环境:在Conda中,你可以使用conda create命令来创建和管理虚拟环境,而使用conda install命令来安装和管理依赖包。以下是一些基本的命令和步骤…...
JVM jstat 查看内存新生代老年代回收情况,排查oom
jstat 命令 jstat - [-t] [-h] [ []] option:我们经常使用的选项有gc、gcutil vmid:java进程id interval:间隔时间,单位为毫秒 count:打印次数 每秒打印一次 jstat -gc 9162 1000S0C:年轻代第一个survivor的容量…...
Postman启动问题:Could not open Postman
Postman启动问题:Could not open Postman 状态,在单击Postman之后一直在转圈圈,无法正常启动。 细心的朋友会发现,右下角 会经常出现防火墙关闭等提示信息,表示该程序,在向外链接。 Error Could not open…...
Golang起步篇(Windows、Linux、mac三种系统安装配置go环境以及IDE推荐以及入门语法详细释义)
Golang起步篇 Golang起步篇一. 安装Go语言开发环境1. Wondows下搭建Go开发环境(1). 下载SDK工具包(2). 解压下载的压缩包,放到特定的目录下,我一般放在d:/programs下(路径不能有中文或者特殊符号如空格等)(3). 配置环境变量步骤1:先打开环境变…...
Error message “error:0308010C:digital envelope routines::unsupported“
1.降级到 Node.js v16。 您可以从 Node.js 的 website 重新安装当前的 LTS 版本。 您也可以使用 nvm。对于 Windows,请使用 nvm-windows。 2.启用传统 OpenSSL 提供程序。 在类 Unix 系统(Linux、macOS、Git bash 等)上: exp…...
解决java在idea运行正常,但是打成jar包后中文乱码问题
目录 比如: 打包命令使用utf-8编码: 1.当在idea中编写的程序,运行一切正常.但是当被打成jar包时,执行的程序会中文乱码.产生问题的原因和解决方案是什么呢? 一.问题分析 分别使用idea和jar包形式打印出System中所有的jvm参数---代码如下: public static…...
数据结构-插入排序+希尔排序+选择排序
目录 1.插入排序 插入排序的时间复杂度: 2.希尔排序 希尔排序的时间复杂度: 3.选择排序 选择排序的时间复杂度: 所谓排序,就是使一串记录,按照其中的某个或某些关键字的大小,递增或递减的排列起来的…...
微信小程序数据传递的方式-页面数据的存取
我们在把数据显示到页面的时候,为了实现良好的互动,都希望在用户点击某个栏目后,获取这个栏目的捆绑数据,然后执行后续的操作。 例如,从数据库里取出对应的记录后,显示在页面上,是一条条的大横条…...
Flutter 应用启动从闪屏页短暂黑屏再到第一个页面
由于应用初始状态启动会有白屏现象,便使用 flutter_native_splash 2.3.5 插件生成了启动相关的配置,并且按照示例使用了 import package:flutter_native_splash/flutter_native_splash.dart;void main() {WidgetsBinding widgetsBinding WidgetsFlutte…...
Linux+qt:获取.so自身的路径(利用dladdr)
目录 1、QDir::currentPath() 2、QAppllication::appllicationDirPath() 3、获取.so自身的路径(利用dladdr) Qt中,也有相关的接口获取程序的相关路径的。 先了解下相关的接口: 1、QDir::currentPath() (1&#x…...
CSS特效014:模仿钟摆效果
CSS常用示例100专栏目录 本专栏记录的是经常使用的CSS示例与技巧,主要包含CSS布局,CSS特效,CSS花边信息三部分内容。其中CSS布局主要是列出一些常用的CSS布局信息点,CSS特效主要是一些动画示例,CSS花边是描述了一些CSS…...
计算机毕业设计选题推荐-个人健康微信小程序/安卓APP-项目实战
✨作者主页:IT研究室✨ 个人简介:曾从事计算机专业培训教学,擅长Java、Python、微信小程序、Golang、安卓Android等项目实战。接项目定制开发、代码讲解、答辩教学、文档编写、降重等。 ☑文末获取源码☑ 精彩专栏推荐⬇⬇⬇ Java项目 Python…...
【自然语言处理(NLP)实战】LSTM网络实现中文文本情感分析(手把手与教学超详细)
目录 引言: 1.所有文件展示: 1.中文停用词数据(hit_stopwords.txt)来源于: 2.其中data数据集为chinese_text_cnn-master.zip提取出的文件。点击链接进入github,点击Code、Download ZIP即可下载。 2.安装依赖库&am…...
迭代新品 | 第四代可燃气体监测仪,守护燃气管网安全快人一步
城市地下市政基础设施是城市有序运行的生命线,事关城市安全、健康运行和高质量发展。近年来,我国燃气事故多发、频发。2020、2021、2022 年分别发生燃气事故668、1140 起、802 起,造成92、106、66 人死亡,560、763、487 人受伤。尤…...
【教3妹学编程-java基础6】详解父子类变量、代码块、构造函数执行顺序
-----------------第二天------------------------ 本文先论述父子类变量、代码块、构造函数执行顺序的结论, 然后通过举例论证,接着再扩展,彻底搞懂静态代码块、动态代码块、构造函数、父子类、类加载机制等知识体系。 温故而知新ÿ…...
深度学习中文汉字识别 计算机竞赛
文章目录 0 前言1 数据集合2 网络构建3 模型训练4 模型性能评估5 文字预测6 最后 0 前言 🔥 优质竞赛项目系列,今天要分享的是 🚩 深度学习中文汉字识别 该项目较为新颖,适合作为竞赛课题方向,学长非常推荐…...
从零开始 通义千问大模型本地化到阿里云通义千问API调用
从零开始 通义千问大模型本地化到阿里云通义千问API调用 一、通义千问大模型介绍 何为“通义千问”? “通义千问大模型”是阿里云推出的一个超大规模的语言模型,具有强大的归纳和理解能力,可以处理各种自然语言处理任务,包括但…...
Linux(3):Linux 的文件权限与目录配置
把具有相同的账户放入到一个组里面,这个组就是这两个账户的 群组 。在访问资源(操作系统中计算机的资源)时,可以让这个组里面的所有用户都具有访问权限。 每个账号都可以有多个群组的支持。 在我们Liux 系统当中,默认的…...
Linux进程——exec族函数、exec族函数与fork函数的配合
exec族函数解析 作用 我们用fork函数创建新进程后,经常会在新进程中调用exec函数去执行另外一个程序。当进程调用exec函数时,该进程被完全替换为新程序。因为调用exec函数并不创建新进程,所以前后进程的ID并没有改变。 功能 在调用进程内部…...
客户端缓存技术
客户端缓存技术主要有以下几种: 内存缓存:客户端(如浏览器)会将请求到的资源(如HTML页面、图片文件等)存储在内存中,以便在再次访问相同资源时可以快速获取,减少向服务器的请求次数…...