当前位置: 首页 > 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;-思维导图】 课本里章节里所有蓝色字体的思维导图...

利用最小二乘法找圆心和半径

#include <iostream> #include <vector> #include <cmath> #include <Eigen/Dense> // 需安装Eigen库用于矩阵运算 // 定义点结构 struct Point { double x, y; Point(double x_, double y_) : x(x_), y(y_) {} }; // 最小二乘法求圆心和半径 …...

在软件开发中正确使用MySQL日期时间类型的深度解析

在日常软件开发场景中&#xff0c;时间信息的存储是底层且核心的需求。从金融交易的精确记账时间、用户操作的行为日志&#xff0c;到供应链系统的物流节点时间戳&#xff0c;时间数据的准确性直接决定业务逻辑的可靠性。MySQL作为主流关系型数据库&#xff0c;其日期时间类型的…...

CVPR 2025 MIMO: 支持视觉指代和像素grounding 的医学视觉语言模型

CVPR 2025 | MIMO&#xff1a;支持视觉指代和像素对齐的医学视觉语言模型 论文信息 标题&#xff1a;MIMO: A medical vision language model with visual referring multimodal input and pixel grounding multimodal output作者&#xff1a;Yanyuan Chen, Dexuan Xu, Yu Hu…...

51c自动驾驶~合集58

我自己的原文哦~ https://blog.51cto.com/whaosoft/13967107 #CCA-Attention 全局池化局部保留&#xff0c;CCA-Attention为LLM长文本建模带来突破性进展 琶洲实验室、华南理工大学联合推出关键上下文感知注意力机制&#xff08;CCA-Attention&#xff09;&#xff0c;…...

C++:std::is_convertible

C++标志库中提供is_convertible,可以测试一种类型是否可以转换为另一只类型: template <class From, class To> struct is_convertible; 使用举例: #include <iostream> #include <string>using namespace std;struct A { }; struct B : A { };int main…...

dedecms 织梦自定义表单留言增加ajax验证码功能

增加ajax功能模块&#xff0c;用户不点击提交按钮&#xff0c;只要输入框失去焦点&#xff0c;就会提前提示验证码是否正确。 一&#xff0c;模板上增加验证码 <input name"vdcode"id"vdcode" placeholder"请输入验证码" type"text&quo…...

智能分布式爬虫的数据处理流水线优化:基于深度强化学习的数据质量控制

在数字化浪潮席卷全球的今天&#xff0c;数据已成为企业和研究机构的核心资产。智能分布式爬虫作为高效的数据采集工具&#xff0c;在大规模数据获取中发挥着关键作用。然而&#xff0c;传统的数据处理流水线在面对复杂多变的网络环境和海量异构数据时&#xff0c;常出现数据质…...

Python ROS2【机器人中间件框架】 简介

销量过万TEEIS德国护膝夏天用薄款 优惠券冠生园 百花蜂蜜428g 挤压瓶纯蜂蜜巨奇严选 鞋子除臭剂360ml 多芬身体磨砂膏280g健70%-75%酒精消毒棉片湿巾1418cm 80片/袋3袋大包清洁食品用消毒 优惠券AIMORNY52朵红玫瑰永生香皂花同城配送非鲜花七夕情人节生日礼物送女友 热卖妙洁棉…...

LabVIEW双光子成像系统技术

双光子成像技术的核心特性 双光子成像通过双低能量光子协同激发机制&#xff0c;展现出显著的技术优势&#xff1a; 深层组织穿透能力&#xff1a;适用于活体组织深度成像 高分辨率观测性能&#xff1a;满足微观结构的精细研究需求 低光毒性特点&#xff1a;减少对样本的损伤…...

一些实用的chrome扩展0x01

简介 浏览器扩展程序有助于自动化任务、查找隐藏的漏洞、隐藏自身痕迹。以下列出了一些必备扩展程序&#xff0c;无论是测试应用程序、搜寻漏洞还是收集情报&#xff0c;它们都能提升工作流程。 FoxyProxy 代理管理工具&#xff0c;此扩展简化了使用代理&#xff08;如 Burp…...