【数据结构】图的存储结构(邻接矩阵)
一.邻接矩阵
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)-思维导图】 课本里章节里所有蓝色字体的思维导图...
铭豹扩展坞 USB转网口 突然无法识别解决方法
当 USB 转网口扩展坞在一台笔记本上无法识别,但在其他电脑上正常工作时,问题通常出在笔记本自身或其与扩展坞的兼容性上。以下是系统化的定位思路和排查步骤,帮助你快速找到故障原因: 背景: 一个M-pard(铭豹)扩展坞的网卡突然无法识别了,扩展出来的三个USB接口正常。…...
【根据当天日期输出明天的日期(需对闰年做判定)。】2022-5-15
缘由根据当天日期输出明天的日期(需对闰年做判定)。日期类型结构体如下: struct data{ int year; int month; int day;};-编程语言-CSDN问答 struct mdata{ int year; int month; int day; }mdata; int 天数(int year, int month) {switch (month){case 1: case 3:…...
ES6从入门到精通:前言
ES6简介 ES6(ECMAScript 2015)是JavaScript语言的重大更新,引入了许多新特性,包括语法糖、新数据类型、模块化支持等,显著提升了开发效率和代码可维护性。 核心知识点概览 变量声明 let 和 const 取代 var…...
反向工程与模型迁移:打造未来商品详情API的可持续创新体系
在电商行业蓬勃发展的当下,商品详情API作为连接电商平台与开发者、商家及用户的关键纽带,其重要性日益凸显。传统商品详情API主要聚焦于商品基本信息(如名称、价格、库存等)的获取与展示,已难以满足市场对个性化、智能…...
中南大学无人机智能体的全面评估!BEDI:用于评估无人机上具身智能体的综合性基准测试
作者:Mingning Guo, Mengwei Wu, Jiarun He, Shaoxian Li, Haifeng Li, Chao Tao单位:中南大学地球科学与信息物理学院论文标题:BEDI: A Comprehensive Benchmark for Evaluating Embodied Agents on UAVs论文链接:https://arxiv.…...
Docker 运行 Kafka 带 SASL 认证教程
Docker 运行 Kafka 带 SASL 认证教程 Docker 运行 Kafka 带 SASL 认证教程一、说明二、环境准备三、编写 Docker Compose 和 jaas文件docker-compose.yml代码说明:server_jaas.conf 四、启动服务五、验证服务六、连接kafka服务七、总结 Docker 运行 Kafka 带 SASL 认…...
苍穹外卖--缓存菜品
1.问题说明 用户端小程序展示的菜品数据都是通过查询数据库获得,如果用户端访问量比较大,数据库访问压力随之增大 2.实现思路 通过Redis来缓存菜品数据,减少数据库查询操作。 缓存逻辑分析: ①每个分类下的菜品保持一份缓存数据…...
零基础设计模式——行为型模式 - 责任链模式
第四部分:行为型模式 - 责任链模式 (Chain of Responsibility Pattern) 欢迎来到行为型模式的学习!行为型模式关注对象之间的职责分配、算法封装和对象间的交互。我们将学习的第一个行为型模式是责任链模式。 核心思想:使多个对象都有机会处…...
基于IDIG-GAN的小样本电机轴承故障诊断
目录 🔍 核心问题 一、IDIG-GAN模型原理 1. 整体架构 2. 核心创新点 (1) 梯度归一化(Gradient Normalization) (2) 判别器梯度间隙正则化(Discriminator Gradient Gap Regularization) (3) 自注意力机制(Self-Attention) 3. 完整损失函数 二…...
【前端异常】JavaScript错误处理:分析 Uncaught (in promise) error
在前端开发中,JavaScript 异常是不可避免的。随着现代前端应用越来越多地使用异步操作(如 Promise、async/await 等),开发者常常会遇到 Uncaught (in promise) error 错误。这个错误是由于未正确处理 Promise 的拒绝(r…...
