【数据结构】图的存储结构(邻接矩阵)
一.邻接矩阵
1.图的特点
任何两个顶点之间都可能存在边,无法通过存储位置表示这种任意的逻辑关系。
图无法采用顺序存储结构。
2.如何存储图?
将顶点与边分开存储。
3.邻接矩阵(数组表示法)
基本思想:
用一个一维数组存储图中顶点的信息,用一个二维数组存储图中各顶点之间的邻接关系。
假设图G有n个顶点,则它的邻接矩阵是一个n*n的方阵

4.无向图的邻接矩阵
1.特点:
无向图的邻接矩阵是一个对称矩阵,主对角线为0
2.如何求顶点i的度?
邻接矩阵的第i行非零元素的个数
3.如何判断顶点i和j之间是否存在边?
判断arc[i][j]是否为1
4.如何求顶点i的所有邻接点?
将数组中第i行元素扫描一遍,若arc[i][j]为1,则顶点j为顶点i的邻接点
5.有向图的邻接矩阵
有向完全图:任意两个顶点之间都有方向相反的弧
1.如何求顶点i的出度?
扫描第i行
2.如何求顶点i的入度?
扫描第i列
6.网图的邻接矩阵

二.邻接矩阵存储无向图的类
const int MAX_VERTEX=10;//图的最大顶点数
template <class T>
class MGraph{
private:T vertex[MAX_VERTEX];int arc[MAX_VERTEX][MAX_VERTEX];int vertexNum,arcNum;//实际顶点个数,边的条数
public:MGraph(T v[],int n,int e);~MGraph();void DFSTraverse(int v);void BFSTraverse(int v);
};
template<class T>
MGraph<T>::MGraph(T v[],int n,int e){int vi,vj;vertexNum=n;arcNum=e;for(int i=0;i<n;i++){vertex[i]=v[i];}for(int i=0;i<n;i++){//初始化邻接矩阵for(int j=0;j<n;j++){arc[i][j]=0;}}for(int i=0;i<e;i++){//依次输入每一条边cin>>vi>>vj;//输入边依附的两个顶点的编号arc[vi][vj]=1;arc[vj][vi]=1;}
}
相关文章:
【数据结构】图的存储结构(邻接矩阵)
一.邻接矩阵 1.图的特点 任何两个顶点之间都可能存在边,无法通过存储位置表示这种任意的逻辑关系。 图无法采用顺序存储结构。 2.如何存储图? 将顶点与边分开存储。 3.邻接矩阵(数组表示法) 基本思想: 用一个一维数…...
kubernetes--Pod控制器详解
目录 一、Pod控制器及其功用: 二、pod控制器的多种类型: 1、ReplicaSet: 1.1 ReplicaSet主要三个组件组成: 2、Deployment: 3、DaemonSet: 4、StatefulSet: 5、Job: 6、Cronjob: …...
九、Linux用户管理
1.基本介绍 Linux系统是一个多用户多任务的操作系统,任何一个要使用系统资源的用户,都必须首先向系统管理员申请一个账号,让后以这个账号的身份进入系统 2.添加用户 基本语法 useradd 用户名 应用案例 案例1:添加一个用户 m…...
springboot项目中没有识别到yml文件解决办法
springboot项目中没有识别到yml文件解决办法 ![外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传] 1、这个意思就是没有配置数据库的数据源路径。所以需要配置数据源,比如mysql的驱动和路径。检查是否在properties或者yml文件中是否已经配置好。…...
[管理与领导-125]:一个IT人的思考:职场中、人际交往中,不要为他人的不良行为和言语买单,不要让自己的情绪被外界影响或掌控。
目录 前言: 一、是什么What 二、为什么Why? 三、怎么办How? 前言: 无论是职场中,还是人际交往中,我们的难免受到他人的影响,有积极正面的情绪影响,有消极负面的情绪影响。为什么我们自身的情绪会受到…...
【FPGA】IP核
一.IP核是什么 IP:知识产权,半导体产业中:在ASIC和FPGA中定义为预先设计好的电路功能模块。 在使用的时候其他用户可以直接调用IP核心。 二. 为什么要是有IP核 提高开发效率,减小设计和调试的时间,加速开发进程&am…...
吾爱破解置顶的“太极”,太好用了吧!
日常工作和娱乐,都需要用到不同类型的软件,哪怕软件体积不大,也必须安装,否则到用时找不到就非常麻烦了。 其实,很多软件不一定一样不剩地全部安装一遍,一方面原因是用的不多,另一方面多少有点…...
Postman接收列表、数组参数@RequestParam List<String> ids
示例如下: 接口定义如下: GetMapping(value "/queryNewMoviePath")public List<Map<String, Object>> queryNewMoviePath(RequestParam List<String> ids ) {return service.queryNewMoviePath(ids);}postman中测试如下: http://loc…...
qemu + busybox + 内核实验环境搭建(2023-11)
主要是参考网上的例子,网上的一些例子可能用的busybox 老旧,编译各种问题,以及rootfs hda的方式或者ramfs的方式。可能有些概念还是不清楚,以下是最终完成测试成功的案例。 下载kernel https://cdn.kernel.org/pub/linux/kernel…...
JavaScript管理HTMLDOM元素(增删改查)
本文主要讲解JavaScript如何通过管理HTML上的DOM元素,其中包括如何查询、创建、修改以及删除具体功能和源码讲解。 增加 首先我们准备一个HTML框架和简单CSS样式,我对其中元素作用和关系进行一个简单说明。 <!DOCTYPE html> <html><he…...
RE2文本匹配实战
引言 今天我们来实现RE2进行文本匹配,模型实现参考了官方代码https://github.com/alibaba-edu/simple-effective-text-matching-pytorch。 模型实现 RE2模型架构如上图所示。它的输入是两个文本片段,所有组件参数除了预测层和对齐层外都是共享的。上图…...
实在智能携手中国电信翼支付,全球首款Agent智能体亮相2023数字科技生态大会
11月10日-13日,中国电信与广东省人民政府联合主办的“2023数字科技生态大会”在广州隆重举行。本届大会以“数字科技焕新启航”为主题,邀请众多生态合作伙伴全方位展示数字科技新成果,包括数字新消费、产业数字化、智能电子、人工智能大模型等…...
安全框架springSecurity+Jwt+Vue-1(vue环境搭建、动态路由、动态标签页)
一、安装vue环境,并新建Vue项目 ①:安装node.js 官网(https://nodejs.org/zh-cn/) 2.安装完成之后检查下版本信息: ②:创建vue项目 1.接下来,我们安装vue的环境 # 安装淘宝npm npm install -g cnpm --registryhttps:/…...
React整理总结(三)
1.props和state的更新 父组件重新render时,所有的子组件也会调用render()函数。shouldComponentUpdate(nextProp, nextState) shouldComponentUpdate(nextProps, nextState) {if (equal(nextProps, this.props) && equa…...
天气这么好,都外出了。顺便了解一下漏桶算法
看到标题,你想到了些什么呢? 又是一个阳光明媚的周末,大家都外出了,路上到处堵车,尤其是各桥梁、隧道入口处,很多车排队等着进入,而出口处就像一个漏桶一样,一辆车接着一辆车有序且…...
【FPGA】Verilog:实现 RS 触发器 | Flip-Flop | 使用 NOR 的 RS 触发器 | 使用 NAND 的 RS 触发器
目录 0x00 RS 触发器(RS Flip-Flop) 0x01 实现 RS 触发器 0x02 使用 NOR 的 RS 触发器 0x03 使用 NAND 的 RS 触发器 0x00 RS 触发器(RS Flip-Flop) 触发器(Flip-Flop)是一种带有时钟的二进制存储设备…...
【技术追踪】SAM(Segment Anything Model)代码解析与结构绘制之Mask Decoder
论文:Segment Anything 代码:https://github.com/facebookresearch/segment-anything 系列篇: (1)【技术追踪】SAM(Segment Anything Model)代码解析与结构绘制之Image Encoder &am…...
认识Tomcat
文章目录 什么是tomcat?tomcat的使用tomcat的下载tomcat的目录结构tomcat的启动在tomcat上部署页面通过浏览器访问部署的页面 学习servlet的原因 什么是tomcat? 盖棺定论:Tomcat是一个HTTP服务器。 我们接下来要长期学习的东西都是关于前后…...
c语言通信之串口通信
在C语言中,可以使用串口通信、网络通信等多种方式实现计算机之间的通信。其中,串口通信通常用于近距离、低速率的通信,而网络通信则适用于远距离、高速率的通信。 下面以串口通信为例,介绍在C语言中如何实现串口通信。 1.打开串…...
软考-高级-系统架构设计师教程(清华第2版)【第16章 嵌入式系统架构设计理论与实践(P555~613)-思维导图】
软考-高级-系统架构设计师教程(清华第2版)【第16章 嵌入式系统架构设计理论与实践(P555~613)-思维导图】 课本里章节里所有蓝色字体的思维导图...
12. 欧姆定律计算器
1. 欧姆定律计算器 功能介绍: 本应用旨在帮助学生快速验证欧姆定律(I=U/RI=U/RI=U/R)的计算关系。用户可以通过滑块...
从零构建ESP32 TWAI CAN库:驱动CyberGear微电机的实践指南
1. ESP32 TWAI CAN库开发背景 第一次接触小米CyberGear微电机时,我遇到了一个棘手的问题:市面上找不到现成的ESP32控制库。这款性能强劲的微型电机采用CAN总线通信,而ESP32内置的TWAI控制器(其实就是CAN控制器)正好可…...
Galaxy新手必看:5分钟搞定生物信息学工作流搭建(附Circos图实战)
Galaxy新手必看:5分钟搞定生物信息学工作流搭建(附Circos图实战) 第一次接触生物信息学分析时,面对命令行和复杂的数据格式,很多初学者都会感到无从下手。Galaxy平台的出现彻底改变了这一局面——这个开源的Web工具让生…...
湿敏电阻(Humidity Sensitive Resistor)气敏电阻
湿敏电阻(Humidity Sensitive Resistor)&气敏电阻 湿敏电阻是一种对环境湿度(尤其是相对湿度 RH)敏感的电阻器, 湿度升高 → 电阻通常降低(多数类型)湿敏电阻器可分为正温度特性湿敏电阻器(阻值随湿度增大而增大)和负温度特性湿敏电阻器(阻值随湿度增大而减小). 本质 利用材…...
零中频接收机设计避坑指南:从IQ信号处理到链路预算,这些细节ADS仿真时千万别忽略
零中频接收机设计避坑指南:从IQ信号处理到链路预算的实战精要 零中频架构在集成化浪潮中展现出独特优势——省去笨重的中频滤波器,直接实现射频到基带的转换。但当你真正用ADS搭建仿真模型时,90度移相器的相位误差可能悄悄吞噬系统EVM指标&am…...
Oracle EBS 资产类别是 真正的树形层级结构(通过弹性域实现父子关系),而 SAP 资产类别(Asset Class)是 扁平结构(无系统内置层级)
Oracle EBS 资产类别是 真正的树形层级结构(通过弹性域实现父子关系),而 SAP 资产类别(Asset Class)是 扁平结构(无系统内置层级)。下面通过详细原理、实例、配置、报表四个维度彻底对比分析。一…...
无人机 Remote ID(RID)广播与技术标准概览
无人机 Remote ID(RID)广播与技术标准概览 目录 概述与知识地图一、RID 广播是什么二、广播内容与工作方式三、广播式 RID 与网络式 RID四、技术要点:频段、功率、硬件与协议五、Open Drone ID / ASTM 报文体系(扩展)…...
直播技术:B站第三方推流方案的实现与应用探索
直播技术:B站第三方推流方案的实现与应用探索 【免费下载链接】bilibili_live_stream_code 用于在准备直播时获取第三方推流码,以便可以绕开哔哩哔哩直播姬,直接在如OBS等软件中进行直播,软件同时提供定义直播分区和标题功能 项…...
2026届最火的降重复率网站横评
Ai论文网站排名(开题报告、文献综述、降aigc率、降重综合对比) TOP1. 千笔AI TOP2. aipasspaper TOP3. 清北论文 TOP4. 豆包 TOP5. kimi TOP6. deepseek 想要有效降低文本 AI 率,针对知网 AI 检测系统独特的识别逻辑,得从语…...
HunterPie终极指南:免费提升怪物猎人世界游戏体验的完整教程
HunterPie终极指南:免费提升怪物猎人世界游戏体验的完整教程 【免费下载链接】HunterPie-legacy A complete, modern and clean overlay with Discord Rich Presence integration for Monster Hunter: World. 项目地址: https://gitcode.com/gh_mirrors/hu/Hunter…...
