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

C++中图的存储

文章目录

      • 0. 实例图
      • 1. 邻接矩阵
      • 2. 邻接矩阵
        • 2.1 链表数组
        • 2.2 链式前向星
      • 3. 参考

0. 实例图

考虑下面这样一个图
在这里插入图片描述

1. 邻接矩阵

vis[i][j] 表示从ij有一条边。直接用二维数组就可以了。

using namespace std;
int vertex_num = 5;
vector<vector<int>> graph(vertex_num, vector<int>(vertex_num, 1));void add_edge(int u, int v){graph[u][v] = 1;
}
bool have_edge(int u,int v) {return graph[u][v];
}

对于上图,矩阵的输出就为:
( 0 1 1 0 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 1 1 0 0 0 0 ) \left ( \begin{array}{} 0 & 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 & 0 \end{array} \right) 0001110000110000010000010

2. 邻接矩阵

对于节点i可达的点都链接在一条链上,而不是存储所有可能边,而是存实际的边。
就像是哈希表一样,链表数组。

在这里插入图片描述

2.1 链表数组

直接用链表数组模拟,还是用vector<vector<int>>

int vertex_num = 5;
vector<vector<int>> adj(5);void add_edge(int u,int v){adj[u].push_back(v);
}
bool find_edge(int u, int v) {for (int i = 0; i < adj[u].size(); ++i) {if (adj[u][i] == v) {return true;}}return false;
}
2.2 链式前向星

把所有边存在了一个数组中而已。即用两个数组模拟上面的过程。
对于以u为入点的边,我们存储时就不能存第一条以u为入点的边了,因为那样不方便插入。所以这种方式加边实际上是链表的尾插法。

我们需要存储以u为入点组成边的链表的头节点(head数组),也就是最后插入的以u为入点的边在边数组中的下标。

注: 图中的加边顺序为边顶点坐标的字符序。

在这里插入图片描述
cnt = edge.size() - 1

上代码

#define MAXN 10000 + 10struct edge {int to;int next;int w;
};struct edge eg[MAXN];
int cnt = -1;
int head[MAXN];void add_edge(int u, int v)
{eg[++cnt].next = head[u];eg[cnt].to = v;head[u] = cnt;
}
bool have_edge(int u, int v)
{for (int i = head[u]; i != -1; i = eg[i].next)if (eg[i].to == v)return true;return false;
}memset(head, -1,sizeof(head));

3. 参考

主要内容是OIWIKI, 只是画图理解下链式前向星。

相关文章:

C++中图的存储

文章目录 0. 实例图1. 邻接矩阵2. 邻接矩阵2.1 链表数组2.2 链式前向星 3. 参考 0. 实例图 考虑下面这样一个图 1. 邻接矩阵 vis[i][j] 表示从i 到j有一条边。直接用二维数组就可以了。 using namespace std; int vertex_num 5; vector<vector<int>> graph(v…...

西瓜书读书笔记整理(七)—— 第七章 贝叶斯分类器

第七章 贝叶斯分类器 7.1 贝叶斯决策论&#xff08;Bayesian Decision Theory&#xff09;7.1.1 先验概率&#xff08;Prior Probability&#xff09;7.1.2 后验概率&#xff08;Posterior Probability&#xff09;7.1.3 似然度&#xff08;Likelihood&#xff09;7.1.4 决策规…...

C#WPF嵌套布局实例

本文演示C#WPF嵌套布局实例。演示了不同布局的简单用法,便于快速应用和掌握。 <Windowx:Class="LayoutDemo.MainWindow"xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation"xmlns:x="http://schemas.microsoft.com/winfx/2006/x…...

Spring和SpringMVC总结

一、Spring IoC(Inversion of Control)中文名称&#xff1a;控制反转&#xff08;对象的创建交给Spring管理&#xff09;。DI(dependency injection )依赖注入。容器&#xff08;Container&#xff09;&#xff1a;放置所有被管理的对象。beans&#xff1a;容器中所有被管理的对…...

C++标准模板(STL)- 类型支持 (类型属性,is_abstract,is_signed,is_unsigned)

类型特性 类型特性定义一个编译时基于模板的结构&#xff0c;以查询或修改类型的属性。 试图特化定义于 <type_traits> 头文件的模板导致未定义行为&#xff0c;除了 std::common_type 可依照其所描述特化。 定义于<type_traits>头文件的模板可以用不完整类型实例…...

前端复制带上版权信息

前端复制带上版权信息 当用户复制内容时&#xff0c;自动添加版权信息。 HTML内容 <body><h1 inputmode"text">复制我</h1> </body>Js内容 document.addEventListener("copy", (event) > {event.preventDefault(); // 阻止…...

【ArcGIS微课1000例】0077:ArcGIS生成经纬网(shp格式)

使用ArcGIS制图的时候,可以很方便的生成经纬网、方里网及参考格网,但是在需要shp格式的经纬网,进一步在南方cass中使用经纬网的时候,就需要单独生成了。 如下图所示为全球大陆矢量数据,我们基于该数据来生成全球指定间距的经纬网数据。 在ArcGIS中,生成经纬网和方里网均…...

读程序员的制胜技笔记04_有用的反模式(下)

1. 重新发明轮子 1.1. 发明家的特质就是要用质疑的心态对待所有事物&#xff0c;你从未停下质疑&#xff0c;那你将不可避免地成为一个发明家 1.2. 并非所有的事情都有现成的轮子可以拿来用 1.3. 自己重新写一个新的API&#xff0c;最终调用你使用的库 1.3.1. 你的API应该是…...

linux驱动开发环境搭建

使用的是parallel 创建的ubuntu 16.04 ubuntu20.04虚拟机 源码准备 # 先查看本机版本 $ uname -r 5.15.0-86-generic# 搜索相关源码 $ sudo apt-cache search linux-source [sudo] password for showme: linux-source - Linux kernel source with Ubuntu patches linux-sourc…...

Qt利用VCPKG和CMake和OpenCV和Tesseract实现中英文OCR

文章目录 1. 开发平台2. 下载文件2.1 下载安装 OpenCV 库2.2 下载安装 Tesseract-OCR库2.3 下载训练好的语言包 3. CMakeLists.txt 内容4. Main.cpp4.1 中英文混合OCR 5. 在Qt Creator 中设置 CMake vcpkg5.1 在初始化配置文件里修改5.2 在构建配置里修改 说明&#xff1a;在Q…...

Day20力扣打卡

打卡记录 数组中两个数的最大异或值&#xff08;位运算&#xff09; 链接 二进制位上从高位向低位进行模拟&#xff0c;看数组中是否有满足此情况的数字。具体题解 class Solution { public:int findMaximumXOR(vector<int>& nums) {int mx *max_element(nums.be…...

设计模式之两阶段终止模式

文章目录 1. 简介 2. 常见思路3. 代码实战 1. 简介 两阶段终止模式&#xff08;Two-Phase Termination Pattern&#xff09;是一种软件设计模式&#xff0c;用于管理线程或进程的生命周期。它包括两个阶段&#xff1a;第一阶段是准备阶段&#xff0c;该阶段用于准备线程或进程…...

Dubbo捕获自定义异常

一.问题描述 Dubbo远程服务提供者抛出的自定义异常无法被消费方正常捕获&#xff0c;消费方捕获的自定义异常全部变成RuntimeException&#xff0c;使用起来很不方便。 二.原因分析 相关源码 /** Licensed to the Apache Software Foundation (ASF) under one or more* con…...

Leetcode刷题详解——求根节点到叶节点数字之和

1. 题目链接&#xff1a;129. 求根节点到叶节点数字之和 2. 题目描述&#xff1a; 给你一个二叉树的根节点 root &#xff0c;树中每个节点都存放有一个 0 到 9 之间的数字。 每条从根节点到叶节点的路径都代表一个数字&#xff1a; 例如&#xff0c;从根节点到叶节点的路径 1…...

emq集群配置nginx做负载均衡

emq集群配置nginx做负载均衡 创建 EMQ X 节点集群 emqx 集群搭建 例如: 节点IP 地址emqx192.168.1.17192.168.1.17emqx192.168.1.18192.168.1.18emqx192.168.1.19192.168.1.19 配置 /etc/nginx/nginx.conf mqtt集群搭建并使用nginx做负载均衡_亲测得结论 示例: vim /et…...

【JAVA学习笔记】60 - 坦克大战1.0-绘图坐标体系、事件处理机制

项目代码 https://github.com/yinhai1114/Java_Learning_Code/tree/main/IDEA_Chapter16/src/com/yinhai 绘图坐标体系 一、基本介绍 下图说明了Java坐标系。坐标原点位于左上角&#xff0c;以像素为单位。在Java坐标系中&#xff0c;第一个是x坐标&#xff0c;表示当前位置为…...

Android13 安装谷歌GMS导致打开蓝牙失败解决方法

Android13 安装谷歌GMS导致打开蓝牙失败解决方法 文章目录 Android13 安装谷歌GMS导致打开蓝牙失败解决方法一、前言二、解决方法1、简单的解决方法2、添加属性和日志解决 三、分析1、查看异常日志2、 查看蓝牙相关日志 四、总结1、Android13 安装谷歌GMS导致打开蓝牙失败具体原…...

独创改进 | RT-DETR 引入双向级联特征融合结构 RepBi-PAN | 附手绘结构图原图

本专栏内容均为博主独家全网首发,未经授权,任何形式的复制、转载、洗稿或传播行为均属违法侵权行为,一经发现将采取法律手段维护合法权益。我们对所有未经授权传播行为保留追究责任的权利。请尊重原创,支持创作者的努力,共同维护网络知识产权。 文章目录 YOLOv6贡献RepBi-…...

Ubuntu下安装vscode,并解决终端打不开vscode的问题

Visual Studio Code安装 1&#xff0c;使用 apt 安装 Visual Studio Code 在官方的微软 Apt 源仓库中可用。按照下面的步骤进行即可&#xff1a; 以 sudo 用户身份运行下面的命令&#xff0c;更新软件包索引&#xff0c;并且安装依赖软件&#xff1a; sudo apt update sud…...

Spring Boot Actuator 漏洞利用

文章目录 前言敏感信息泄露env 泄露配置信息trace 泄露用户请求信息mappings 泄露路由信息heapdump泄露堆栈信息 前言 spring对应两个版本&#xff0c;分别是Spring Boot 2.x和Spring Boot 1.x&#xff0c;因此后面漏洞利用的payload也会有所不同 敏感信息泄露 env 泄露配置信…...

docker详细操作--未完待续

docker介绍 docker官网: Docker&#xff1a;加速容器应用程序开发 harbor官网&#xff1a;Harbor - Harbor 中文 使用docker加速器: Docker镜像极速下载服务 - 毫秒镜像 是什么 Docker 是一种开源的容器化平台&#xff0c;用于将应用程序及其依赖项&#xff08;如库、运行时环…...

简易版抽奖活动的设计技术方案

1.前言 本技术方案旨在设计一套完整且可靠的抽奖活动逻辑,确保抽奖活动能够公平、公正、公开地进行,同时满足高并发访问、数据安全存储与高效处理等需求,为用户提供流畅的抽奖体验,助力业务顺利开展。本方案将涵盖抽奖活动的整体架构设计、核心流程逻辑、关键功能实现以及…...

Redis相关知识总结(缓存雪崩,缓存穿透,缓存击穿,Redis实现分布式锁,如何保持数据库和缓存一致)

文章目录 1.什么是Redis&#xff1f;2.为什么要使用redis作为mysql的缓存&#xff1f;3.什么是缓存雪崩、缓存穿透、缓存击穿&#xff1f;3.1缓存雪崩3.1.1 大量缓存同时过期3.1.2 Redis宕机 3.2 缓存击穿3.3 缓存穿透3.4 总结 4. 数据库和缓存如何保持一致性5. Redis实现分布式…...

2024年赣州旅游投资集团社会招聘笔试真

2024年赣州旅游投资集团社会招聘笔试真 题 ( 满 分 1 0 0 分 时 间 1 2 0 分 钟 ) 一、单选题(每题只有一个正确答案,答错、不答或多答均不得分) 1.纪要的特点不包括()。 A.概括重点 B.指导传达 C. 客观纪实 D.有言必录 【答案】: D 2.1864年,()预言了电磁波的存在,并指出…...

1688商品列表API与其他数据源的对接思路

将1688商品列表API与其他数据源对接时&#xff0c;需结合业务场景设计数据流转链路&#xff0c;重点关注数据格式兼容性、接口调用频率控制及数据一致性维护。以下是具体对接思路及关键技术点&#xff1a; 一、核心对接场景与目标 商品数据同步 场景&#xff1a;将1688商品信息…...

高等数学(下)题型笔记(八)空间解析几何与向量代数

目录 0 前言 1 向量的点乘 1.1 基本公式 1.2 例题 2 向量的叉乘 2.1 基础知识 2.2 例题 3 空间平面方程 3.1 基础知识 3.2 例题 4 空间直线方程 4.1 基础知识 4.2 例题 5 旋转曲面及其方程 5.1 基础知识 5.2 例题 6 空间曲面的法线与切平面 6.1 基础知识 6.2…...

精益数据分析(97/126):邮件营销与用户参与度的关键指标优化指南

精益数据分析&#xff08;97/126&#xff09;&#xff1a;邮件营销与用户参与度的关键指标优化指南 在数字化营销时代&#xff0c;邮件列表效度、用户参与度和网站性能等指标往往决定着创业公司的增长成败。今天&#xff0c;我们将深入解析邮件打开率、网站可用性、页面参与时…...

视觉slam十四讲实践部分记录——ch2、ch3

ch2 一、使用g++编译.cpp为可执行文件并运行(P30) g++ helloSLAM.cpp ./a.out运行 二、使用cmake编译 mkdir build cd build cmake .. makeCMakeCache.txt 文件仍然指向旧的目录。这表明在源代码目录中可能还存在旧的 CMakeCache.txt 文件,或者在构建过程中仍然引用了旧的路…...

【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的“no matching...“系列算法协商失败问题

【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的"no matching..."系列算法协商失败问题 摘要&#xff1a; 近期&#xff0c;在使用较新版本的OpenSSH客户端连接老旧SSH服务器时&#xff0c;会遇到 "no matching key exchange method found"​, "n…...

Selenium常用函数介绍

目录 一&#xff0c;元素定位 1.1 cssSeector 1.2 xpath 二&#xff0c;操作测试对象 三&#xff0c;窗口 3.1 案例 3.2 窗口切换 3.3 窗口大小 3.4 屏幕截图 3.5 关闭窗口 四&#xff0c;弹窗 五&#xff0c;等待 六&#xff0c;导航 七&#xff0c;文件上传 …...