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(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 贝叶斯决策论(Bayesian Decision Theory)7.1.1 先验概率(Prior Probability)7.1.2 后验概率(Posterior Probability)7.1.3 似然度(Likelihood)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)中文名称:控制反转(对象的创建交给Spring管理)。DI(dependency injection )依赖注入。容器(Container):放置所有被管理的对象。beans:容器中所有被管理的对…...

C++标准模板(STL)- 类型支持 (类型属性,is_abstract,is_signed,is_unsigned)
类型特性 类型特性定义一个编译时基于模板的结构,以查询或修改类型的属性。 试图特化定义于 <type_traits> 头文件的模板导致未定义行为,除了 std::common_type 可依照其所描述特化。 定义于<type_traits>头文件的模板可以用不完整类型实例…...
前端复制带上版权信息
前端复制带上版权信息 当用户复制内容时,自动添加版权信息。 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. 发明家的特质就是要用质疑的心态对待所有事物,你从未停下质疑,那你将不可避免地成为一个发明家 1.2. 并非所有的事情都有现成的轮子可以拿来用 1.3. 自己重新写一个新的API,最终调用你使用的库 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 在构建配置里修改 说明:在Q…...

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

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

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

Leetcode刷题详解——求根节点到叶节点数字之和
1. 题目链接:129. 求根节点到叶节点数字之和 2. 题目描述: 给你一个二叉树的根节点 root ,树中每个节点都存放有一个 0 到 9 之间的数字。 每条从根节点到叶节点的路径都代表一个数字: 例如,从根节点到叶节点的路径 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坐标系。坐标原点位于左上角,以像素为单位。在Java坐标系中,第一个是x坐标,表示当前位置为…...
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,使用 apt 安装 Visual Studio Code 在官方的微软 Apt 源仓库中可用。按照下面的步骤进行即可: 以 sudo 用户身份运行下面的命令,更新软件包索引,并且安装依赖软件: sudo apt update sud…...

Spring Boot Actuator 漏洞利用
文章目录 前言敏感信息泄露env 泄露配置信息trace 泄露用户请求信息mappings 泄露路由信息heapdump泄露堆栈信息 前言 spring对应两个版本,分别是Spring Boot 2.x和Spring Boot 1.x,因此后面漏洞利用的payload也会有所不同 敏感信息泄露 env 泄露配置信…...
基于算法竞赛的c++编程(28)结构体的进阶应用
结构体的嵌套与复杂数据组织 在C中,结构体可以嵌套使用,形成更复杂的数据结构。例如,可以通过嵌套结构体描述多层级数据关系: struct Address {string city;string street;int zipCode; };struct Employee {string name;int id;…...

业务系统对接大模型的基础方案:架构设计与关键步骤
业务系统对接大模型:架构设计与关键步骤 在当今数字化转型的浪潮中,大语言模型(LLM)已成为企业提升业务效率和创新能力的关键技术之一。将大模型集成到业务系统中,不仅可以优化用户体验,还能为业务决策提供…...
vscode里如何用git
打开vs终端执行如下: 1 初始化 Git 仓库(如果尚未初始化) git init 2 添加文件到 Git 仓库 git add . 3 使用 git commit 命令来提交你的更改。确保在提交时加上一个有用的消息。 git commit -m "备注信息" 4 …...
利用ngx_stream_return_module构建简易 TCP/UDP 响应网关
一、模块概述 ngx_stream_return_module 提供了一个极简的指令: return <value>;在收到客户端连接后,立即将 <value> 写回并关闭连接。<value> 支持内嵌文本和内置变量(如 $time_iso8601、$remote_addr 等)&a…...

安宝特方案丨XRSOP人员作业标准化管理平台:AR智慧点检验收套件
在选煤厂、化工厂、钢铁厂等过程生产型企业,其生产设备的运行效率和非计划停机对工业制造效益有较大影响。 随着企业自动化和智能化建设的推进,需提前预防假检、错检、漏检,推动智慧生产运维系统数据的流动和现场赋能应用。同时,…...
Linux简单的操作
ls ls 查看当前目录 ll 查看详细内容 ls -a 查看所有的内容 ls --help 查看方法文档 pwd pwd 查看当前路径 cd cd 转路径 cd .. 转上一级路径 cd 名 转换路径 …...

家政维修平台实战20:权限设计
目录 1 获取工人信息2 搭建工人入口3 权限判断总结 目前我们已经搭建好了基础的用户体系,主要是分成几个表,用户表我们是记录用户的基础信息,包括手机、昵称、头像。而工人和员工各有各的表。那么就有一个问题,不同的角色…...
使用van-uploader 的UI组件,结合vue2如何实现图片上传组件的封装
以下是基于 vant-ui(适配 Vue2 版本 )实现截图中照片上传预览、删除功能,并封装成可复用组件的完整代码,包含样式和逻辑实现,可直接在 Vue2 项目中使用: 1. 封装的图片上传组件 ImageUploader.vue <te…...

高危文件识别的常用算法:原理、应用与企业场景
高危文件识别的常用算法:原理、应用与企业场景 高危文件识别旨在检测可能导致安全威胁的文件,如包含恶意代码、敏感数据或欺诈内容的文档,在企业协同办公环境中(如Teams、Google Workspace)尤为重要。结合大模型技术&…...

WordPress插件:AI多语言写作与智能配图、免费AI模型、SEO文章生成
厌倦手动写WordPress文章?AI自动生成,效率提升10倍! 支持多语言、自动配图、定时发布,让内容创作更轻松! AI内容生成 → 不想每天写文章?AI一键生成高质量内容!多语言支持 → 跨境电商必备&am…...