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

【数据结构】图的存储结构(邻接矩阵)

一.邻接矩阵

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.图的特点 任何两个顶点之间都可能存在边&#xff0c;无法通过存储位置表示这种任意的逻辑关系。 图无法采用顺序存储结构。 2.如何存储图&#xff1f; 将顶点与边分开存储。 3.邻接矩阵&#xff08;数组表示法&#xff09; 基本思想&#xff1a; 用一个一维数…...

kubernetes--Pod控制器详解

目录 一、Pod控制器及其功用&#xff1a; 二、pod控制器的多种类型&#xff1a; 1、ReplicaSet: 1.1 ReplicaSet主要三个组件组成&#xff1a; 2、Deployment&#xff1a; 3、DaemonSet&#xff1a; 4、StatefulSet&#xff1a; 5、Job&#xff1a; 6、Cronjob&#xff1a; …...

九、Linux用户管理

1.基本介绍 Linux系统是一个多用户多任务的操作系统&#xff0c;任何一个要使用系统资源的用户&#xff0c;都必须首先向系统管理员申请一个账号&#xff0c;让后以这个账号的身份进入系统 2.添加用户 基本语法 useradd 用户名 应用案例 案例1&#xff1a;添加一个用户 m…...

springboot项目中没有识别到yml文件解决办法

springboot项目中没有识别到yml文件解决办法 ![外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传] 1、这个意思就是没有配置数据库的数据源路径。所以需要配置数据源&#xff0c;比如mysql的驱动和路径。检查是否在properties或者yml文件中是否已经配置好。…...

[管理与领导-125]:一个IT人的思考:职场中、人际交往中,不要为他人的不良行为和言语买单,不要让自己的情绪被外界影响或掌控。

目录 前言&#xff1a; 一、是什么What 二、为什么Why? 三、怎么办How? 前言&#xff1a; 无论是职场中&#xff0c;还是人际交往中&#xff0c;我们的难免受到他人的影响&#xff0c;有积极正面的情绪影响&#xff0c;有消极负面的情绪影响。为什么我们自身的情绪会受到…...

【FPGA】IP核

一.IP核是什么 IP&#xff1a;知识产权&#xff0c;半导体产业中&#xff1a;在ASIC和FPGA中定义为预先设计好的电路功能模块。 在使用的时候其他用户可以直接调用IP核心。 二. 为什么要是有IP核 提高开发效率&#xff0c;减小设计和调试的时间&#xff0c;加速开发进程&am…...

吾爱破解置顶的“太极”,太好用了吧!

日常工作和娱乐&#xff0c;都需要用到不同类型的软件&#xff0c;哪怕软件体积不大&#xff0c;也必须安装&#xff0c;否则到用时找不到就非常麻烦了。 其实&#xff0c;很多软件不一定一样不剩地全部安装一遍&#xff0c;一方面原因是用的不多&#xff0c;另一方面多少有点…...

Postman接收列表、数组参数@RequestParam List<String> ids

示例如下: 接口定义如下: GetMapping(value "/queryNewMoviePath")public List<Map<String, Object>> queryNewMoviePath(RequestParam List<String> ids ) {return service.queryNewMoviePath(ids);}postman中测试如下&#xff1a; http://loc…...

qemu + busybox + 内核实验环境搭建(2023-11)

主要是参考网上的例子&#xff0c;网上的一些例子可能用的busybox 老旧&#xff0c;编译各种问题&#xff0c;以及rootfs hda的方式或者ramfs的方式。可能有些概念还是不清楚&#xff0c;以下是最终完成测试成功的案例。 下载kernel https://cdn.kernel.org/pub/linux/kernel…...

JavaScript管理HTMLDOM元素(增删改查)

本文主要讲解JavaScript如何通过管理HTML上的DOM元素&#xff0c;其中包括如何查询、创建、修改以及删除具体功能和源码讲解。 增加 首先我们准备一个HTML框架和简单CSS样式&#xff0c;我对其中元素作用和关系进行一个简单说明。 <!DOCTYPE html> <html><he…...

RE2文本匹配实战

引言 今天我们来实现RE2进行文本匹配&#xff0c;模型实现参考了官方代码https://github.com/alibaba-edu/simple-effective-text-matching-pytorch。 模型实现 RE2模型架构如上图所示。它的输入是两个文本片段&#xff0c;所有组件参数除了预测层和对齐层外都是共享的。上图…...

实在智能携手中国电信翼支付,全球首款Agent智能体亮相2023数字科技生态大会

11月10日-13日&#xff0c;中国电信与广东省人民政府联合主办的“2023数字科技生态大会”在广州隆重举行。本届大会以“数字科技焕新启航”为主题&#xff0c;邀请众多生态合作伙伴全方位展示数字科技新成果&#xff0c;包括数字新消费、产业数字化、智能电子、人工智能大模型等…...

安全框架springSecurity+Jwt+Vue-1(vue环境搭建、动态路由、动态标签页)

一、安装vue环境&#xff0c;并新建Vue项目 ①&#xff1a;安装node.js 官网(https://nodejs.org/zh-cn/) 2.安装完成之后检查下版本信息&#xff1a; ②&#xff1a;创建vue项目 1.接下来&#xff0c;我们安装vue的环境 # 安装淘宝npm npm install -g cnpm --registryhttps:/…...

React整理总结(三)

1.props和state的更新 父组件重新render时&#xff0c;所有的子组件也会调用render()函数。shouldComponentUpdate&#xff08;nextProp&#xff0c; nextState&#xff09; shouldComponentUpdate(nextProps, nextState) {if (equal(nextProps, this.props) && equa…...

天气这么好,都外出了。顺便了解一下漏桶算法

看到标题&#xff0c;你想到了些什么呢&#xff1f; 又是一个阳光明媚的周末&#xff0c;大家都外出了&#xff0c;路上到处堵车&#xff0c;尤其是各桥梁、隧道入口处&#xff0c;很多车排队等着进入&#xff0c;而出口处就像一个漏桶一样&#xff0c;一辆车接着一辆车有序且…...

【FPGA】Verilog:实现 RS 触发器 | Flip-Flop | 使用 NOR 的 RS 触发器 | 使用 NAND 的 RS 触发器

目录 0x00 RS 触发器&#xff08;RS Flip-Flop&#xff09; 0x01 实现 RS 触发器 0x02 使用 NOR 的 RS 触发器 0x03 使用 NAND 的 RS 触发器 0x00 RS 触发器&#xff08;RS Flip-Flop&#xff09; 触发器&#xff08;Flip-Flop&#xff09;是一种带有时钟的二进制存储设备…...

【技术追踪】SAM(Segment Anything Model)代码解析与结构绘制之Mask Decoder

论文&#xff1a;Segment Anything   代码&#xff1a;https://github.com/facebookresearch/segment-anything 系列篇&#xff1a;   &#xff08;1&#xff09;【技术追踪】SAM&#xff08;Segment Anything Model&#xff09;代码解析与结构绘制之Image Encoder   &am…...

认识Tomcat

文章目录 什么是tomcat&#xff1f;tomcat的使用tomcat的下载tomcat的目录结构tomcat的启动在tomcat上部署页面通过浏览器访问部署的页面 学习servlet的原因 什么是tomcat&#xff1f; 盖棺定论&#xff1a;Tomcat是一个HTTP服务器。 我们接下来要长期学习的东西都是关于前后…...

c语言通信之串口通信

在C语言中&#xff0c;可以使用串口通信、网络通信等多种方式实现计算机之间的通信。其中&#xff0c;串口通信通常用于近距离、低速率的通信&#xff0c;而网络通信则适用于远距离、高速率的通信。 下面以串口通信为例&#xff0c;介绍在C语言中如何实现串口通信。 1.打开串…...

​软考-高级-系统架构设计师教程(清华第2版)【第16章 嵌入式系统架构设计理论与实践(P555~613)-思维导图】​

软考-高级-系统架构设计师教程&#xff08;清华第2版&#xff09;【第16章 嵌入式系统架构设计理论与实践&#xff08;P555~613&#xff09;-思维导图】 课本里章节里所有蓝色字体的思维导图...

接口测试中缓存处理策略

在接口测试中&#xff0c;缓存处理策略是一个关键环节&#xff0c;直接影响测试结果的准确性和可靠性。合理的缓存处理策略能够确保测试环境的一致性&#xff0c;避免因缓存数据导致的测试偏差。以下是接口测试中常见的缓存处理策略及其详细说明&#xff1a; 一、缓存处理的核…...

变量 varablie 声明- Rust 变量 let mut 声明与 C/C++ 变量声明对比分析

一、变量声明设计&#xff1a;let 与 mut 的哲学解析 Rust 采用 let 声明变量并通过 mut 显式标记可变性&#xff0c;这种设计体现了语言的核心哲学。以下是深度解析&#xff1a; 1.1 设计理念剖析 安全优先原则&#xff1a;默认不可变强制开发者明确声明意图 let x 5; …...

vscode(仍待补充)

写于2025 6.9 主包将加入vscode这个更权威的圈子 vscode的基本使用 侧边栏 vscode还能连接ssh&#xff1f; debug时使用的launch文件 1.task.json {"tasks": [{"type": "cppbuild","label": "C/C: gcc.exe 生成活动文件"…...

java调用dll出现unsatisfiedLinkError以及JNA和JNI的区别

UnsatisfiedLinkError 在对接硬件设备中&#xff0c;我们会遇到使用 java 调用 dll文件 的情况&#xff0c;此时大概率出现UnsatisfiedLinkError链接错误&#xff0c;原因可能有如下几种 类名错误包名错误方法名参数错误使用 JNI 协议调用&#xff0c;结果 dll 未实现 JNI 协…...

NFT模式:数字资产确权与链游经济系统构建

NFT模式&#xff1a;数字资产确权与链游经济系统构建 ——从技术架构到可持续生态的范式革命 一、确权技术革新&#xff1a;构建可信数字资产基石 1. 区块链底层架构的进化 跨链互操作协议&#xff1a;基于LayerZero协议实现以太坊、Solana等公链资产互通&#xff0c;通过零知…...

音视频——I2S 协议详解

I2S 协议详解 I2S (Inter-IC Sound) 协议是一种串行总线协议&#xff0c;专门用于在数字音频设备之间传输数字音频数据。它由飞利浦&#xff08;Philips&#xff09;公司开发&#xff0c;以其简单、高效和广泛的兼容性而闻名。 1. 信号线 I2S 协议通常使用三根或四根信号线&a…...

nnUNet V2修改网络——暴力替换网络为UNet++

更换前,要用nnUNet V2跑通所用数据集,证明nnUNet V2、数据集、运行环境等没有问题 阅读nnU-Net V2 的 U-Net结构,初步了解要修改的网络,知己知彼,修改起来才能游刃有余。 U-Net存在两个局限,一是网络的最佳深度因应用场景而异,这取决于任务的难度和可用于训练的标注数…...

stm32wle5 lpuart DMA数据不接收

配置波特率9600时&#xff0c;需要使用外部低速晶振...

【深尚想】TPS54618CQRTERQ1汽车级同步降压转换器电源芯片全面解析

1. 元器件定义与技术特点 TPS54618CQRTERQ1 是德州仪器&#xff08;TI&#xff09;推出的一款 汽车级同步降压转换器&#xff08;DC-DC开关稳压器&#xff09;&#xff0c;属于高性能电源管理芯片。核心特性包括&#xff1a; 输入电压范围&#xff1a;2.95V–6V&#xff0c;输…...

大模型——基于Docker+DeepSeek+Dify :搭建企业级本地私有化知识库超详细教程

基于Docker+DeepSeek+Dify :搭建企业级本地私有化知识库超详细教程 下载安装Docker Docker官网:https://www.docker.com/ 自定义Docker安装路径 Docker默认安装在C盘,大小大概2.9G,做这行最忌讳的就是安装软件全装C盘,所以我调整了下安装路径。 新建安装目录:E:\MyS…...