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

数据结构图论基础知识（一）

news 来源：原创 2025/7/20 10:51:15

文章目录

1. 图的基本概念
2. 图的一些现实的应用
- 2.1 ABCDE各个城市之间的关系
- 2.2 社交关系
3. 图的存储结构
- 3.1邻接矩阵
- 3.2 邻接矩阵的实现
- 3.3 邻接表

1. 图的基本概念

1. （graph）图由边（edge）和顶点（Vertex）构成
2. 图是由顶点集合及顶点间的关系组成的一种数据结构：G = (V， E)，其中：顶点集合V = {x|x属于某个数据对象集}是有穷非空集合
3. E = {(x,y)|x,y属于V}或者E = {<x, y>|x,y属于V && Path(x, y)}是顶点间关系的有穷集合，也叫做边的集合。
4. 图更关注元素与元素之间的关系
5. 图分为有向图和无向图
6. 二叉树也是图吗？
树是一种特殊的（无环联通图）图，但是图不一定是树，再者树关心的是节点中存的值，图关注的是顶点和边的权值

在这里插入图片描述

2. 图的一些现实的应用

2.1 ABCDE各个城市之间的关系

1. 顶点：城市
2. 边：城市之间的关系（比如它们之间的距离，到达的时间，）
3. 保证联通情况下的最小开销，D点要到达B点的最小距离就可以是一个最小生成树的问题
4. 最小生成树：用最小的代价，把图中的两个点间接地连在一起

在这里插入图片描述

2.2 社交关系

1. 顶点：人
2. 边：表示两个人是好友
3. 权值：可以表示两个人之间的亲密度
4. qq，微信等都是无向图，是强社交关系：表示两个人互相都是好友
5. 微博，抖音等都是有向图，是社交媒体关系，是弱社交关系：我可以关注喜欢的博主，但是博主不一定关注了我

在这里插入图片描述

3. 图的存储结构

3.1邻接矩阵

1. 因为节点与节点之间的关系就是连通与否，即为0或者1，因此邻接矩阵(二维数组)即是：先用一个数组将定点保存，然后采用矩阵来表示节点与节点之间的关系。

在这里插入图片描述
2. 无向图的邻接矩阵是对称的，第i行(列)元素之和，就是顶点i的度。有向图的邻接矩阵则不一定是对称的，第i行(列)元素之后就是顶点i 的出(入)度。
3. 如果边带有权值，并且两个节点之间是连通的，上图中的边的关系就用权值代替，如果两个顶点不通，则使用无穷大代替。

在这里插入图片描述
4. 用邻接矩阵存储图的好处是能够快速知道两个顶点是否连通O(1)，缺陷是如果顶点比较多，边比较少时，矩阵中存储了大量的0成为系数矩阵，比较浪费空间，并且要求两个节点之间的路径不是很好求，不适合查找一个顶点所连接的所有边O(N)，比如查找3这个顶点的所有边，要看0，1，2，3是否为1，也就是要查找N次

在这里插入图片描述

3.2 邻接矩阵的实现

#pragma once#include<iostream>
#include<vector>
#include<string>
#include<map>
using namespace std;// 邻接矩阵
namespace matrix
{// 无向图,V顶点,W边template<class V,class W,W MAX_W = INT_MAX,bool Direction = false>class Graph{public:// 图创建的方式：// 1.io输入,不方便测试,oj测试比较方便// 2.图的结构写到文件中,读取文件// 3.手动添加边,方便测试// 图的初始化Graph(const V* a, size_t n)// 传一个顶点相关的集合进行初始化{// 顶点的集合_vertexs.reserve(n);for (size_t i = 0; i < n; i++){_vertexs.push_back(a[i]);_indexMap[a[i]] = i;// 顶点和下标的映射}_matrix.resize(n);for (int i = 0; i < _matrix.size(); i++){_matrix[i].resize(n,MAX_W);}}// 获取顶点的下标,检查顶点是否是错误的size_t GetVertexIndex(const V& v){auto it = _indexMap.find(v);if (it != _indexMap.end()){return it->second;}else{// 抛异常throw invalid_argument("顶点不存在");return -1;}}// 给序号为两个节点的添加边(权值)void AddEdge(const V& src,const V& dst,const W& w){size_t srci = GetVertexIndex(src);size_t dsti = GetVertexIndex(dst);_matrix[srci][dsti] = w;// 无向图需要添加两个有关联的边if (Direction == false) _matrix[dsti][srci] = w;}// 打印void Print(){// 顶点for (int i = 0; i < _vertexs.size(); i++){cout << "[" << i << "]" << "->" << _vertexs[i] << '\n';}cout << '\n';cout << "  ";// 横着的下标for (int i = 0; i < _vertexs.size(); i++){cout << i << " ";}cout << '\n';// 邻接矩阵for (int i = 0; i < _matrix.size(); i++){// 竖着的下标cout << i << " ";for (int j = 0; j < _matrix[i].size(); j++){if (_matrix[i][j] == MAX_W){cout << "*" << " ";}elsecout << _matrix[i][j] << " ";}cout << '\n';}}private:vector<V> _vertexs;// 顶点集合map<V, int> _indexMap;// 顶点映射下标vector<vector<W>> _matrix;// 邻接矩阵};void TestGraph(){char vertices[] = { '0', '1', '2', '3' };  // 显式传入 char 数组Graph<char, int, INT_MAX, true> g(vertices, 4);g.AddEdge('0', '1', 1);g.AddEdge('0', '3', 4);g.AddEdge('1', '3', 2);g.AddEdge('1', '2', 9);g.AddEdge('2', '3', 8);g.AddEdge('2', '1', 5);g.AddEdge('2', '0', 3);g.AddEdge('3', '2', 6);g.Print();}
}#include"Graph.h"
using namespace std;int main()
{matrix::TestGraph();return 0;
}

3.3 邻接表

邻接表：使用数组表示顶点的集合，使用链表表示边的关系。
1.无向图邻接表存储
在这里插入图片描述
2. 有向图邻接表存储，一般情况下，存储一个出边表即可，主要是为了找到一个顶点连接出去的路径有哪些

在这里插入图片描述

总结一下，邻接矩阵和邻接表是相辅相成的关系，各有优缺点，两者具有互补的关系

在这里插入图片描述

数据结构图论基础知识（一）

文章目录 1. 图的基本概念2. 图的一些现实的应用2.1 ABCDE各个城市之间的关系2.2 社交关系 3. 图的存储结构3.1邻接矩阵3.2 邻接矩阵的实现3.3 邻接表 1. 图的基本概念 1. （graph）图由边（edge）和顶点（Vertex&#xff…...

编程日记 2025/7/20 10:51:15

安宝特案例 | AR如何大幅提升IC封装厂检测效率？

前言：如何提升IC封装厂检测效率？ 在现代电子产品的制造过程中，IC封装作为核心环节，涉及到复杂处理流程和严格质量检测。这是一家专注于IC封装的厂商，负责将来自IC制造商的晶圆进行保护、散热和导通处理。整个制程繁琐…...

编程日记 2025/7/20 9:42:02

2024年ESWA SCI1区TOP：量子计算蜣螂算法QHDBO，深度解析+性能实测

目录 1.摘要2.蜣螂优化算法DBO原理3.改进策略4.结果展示5.参考文献6.代码获取 1.摘要蜣螂优化算法是一种群体智能优化算法，具有较强的优化能力和快速收敛性，但容易在优化过程后期陷入局部最优解。本文提出了一种量子计算和多策略混合的蜣螂优化算法&am…...

编程日记 2025/7/20 9:39:19

数据结构*链表- LinkedList

什么是链表相较于ArrayList顺序表来说，链表是物理存储结构上非连续存储结构（也就是地址不是连续的）。链表由一系列节点构成，每个节点包含数据和指向下一个节点的引用。链表的各个节点在内存里并非连续存储，而是通过引…...

编程日记 2025/7/20 10:39:54

WebRTC服务器Coturn服务器用户管理和安全性

1、概述 Coturn服务器对用户管理和安全方面也做了很多的措施，以下会介绍到用户方面的设置 1.1、相关术语 1.1.1 realm 在 coturn 服务器中，域（realm）是一种逻辑上的分组概念，用于对不同的用户群体、应用或者服务进行区…...

编程日记 2025/7/20 10:27:32

MySQL聚簇索引和非聚簇索引

聚簇索引（Clustered Index）和非聚簇索引（Non-Clustered Index）是数据库中常用的两种索引类型，它们在数据存储和检索方式上有显著的区别。一、聚簇索引（Clustered Index） 聚簇索引是数据表中的…...

编程日记 2025/7/20 10:28:39

QT加入阿里云OSS上传图片SDK，编译报错：error LNK2019: 无法解析的外部符号 EVP_MD_CTX_init

参考此链接把OSS上传图片的SDK，cmake成lib库，如下图将lib库放入自己的项目文件夹下，并在pro文件中添加此lib库。而解决 “无法解析的外部符号 EVP_MD_CTX_init” 问题，则需要将third_party文件夹下的一些依赖库和头文件都放到自己…...

编程日记 2025/7/20 10:43:58

正点原子TFTLCD扩展

声明：该文章代码是在正点原子教学下写出的LCD驱动代码上进行了修改能兼容更多字号( ˘ ˘)❤️ 如有侵权，请私信联系删除文章目录前言代码lcd.clcd.hfont.h 前言由于TFTLCD4.3寸屏幕太大了，正点原子的代码只能显示12/16/24字号的字符或者…...

编程日记 2025/7/20 10:35:18

部署Megatron - LM，快速上手使用

安装Megatron - LM 首先检查一下当前环境是否已经有 NVIDIA 驱动和 CUDA： nvidia-smi 直接在当前环境安装运行 PyTorch 和 Megatron-LM不使用 Docker 之前我们看到目前的环境有 NVIDIA V100 GPU 和 CUDA 12.1，我们可以安装对应的 GPU 版本 PyTorch。…...

编程日记 2025/7/20 10:39:55

赛灵思 XC7K325T-2FFG900I FPGA Xilinx Kintex‑7

XC7K325T-2FFG900I 是 Xilinx Kintex‑7 系列中一款工业级 (I) 高性能 FPGA，基于 28 nm HKMG HPL 工艺制程，核心电压标称 1.0 V，I/O 电压可在 0.97 V–1.03 V 之间灵活配置，并可在 –40 C 至 100 C 温度范围内稳定运行。该器件提供…...

编程日记 2025/7/20 10:21:23

20.1Linux的PWM驱动实验(知识点)_csdn

PWM 是很常用到功能，我们可以通过 PWM 来控制电机速度，也可以使用 PWM 来控制LCD 的背光亮度。本章我们就来学习一下如何在 Linux 下进行 PWM 驱动开发。在之前学过STM32的就知道这部分内容，利用占空比来调节电机的转速。 1、PWM 驱动简析 …...

编程日记 2025/6/29 9:37:17

如何在 Java 中从 PDF 文件中删除页面（教程）

由于 PDF 文件格式不是 Java 原生支持的，因此要从 PDF 中删除页面，你需要使用外部库。本教程介绍如何使用 JPedal 来实现这一功能。开始使用 • 将 JPedal 添加到你的类路径或模块路径中（可从官网下载安装试用版 JAR 文件） •…...

编程日记 2025/6/29 11:48:46

2026《数据结构》考研复习笔记五（栈、队列）

栈、队列一、栈1.卡特兰数2.不合法的出栈序列二、队列1.循环队列2.输入输出受限队列（四个数1234） 三、算法1.栈在括号匹配中的应用2.中缀表达式求值（通过转化为后缀表达式再后缀表达式求值）3.中缀表达式转化为后缀表达式4.后缀表…...

编程日记 2025/6/29 9:47:41

本地部署DeepSeek大模型

本地部署 ollama 下载Ollama ollama支持的模型：Ollama Search 直接下载，发现默认是下载C盘，并且不能选择安装目录，这对我C盘的压力太大了。查阅资料：发现可以修改参考将Ollama安装到非C盘路径_ollama不安装在c盘…...

编程日记 2025/6/29 9:37:19

C++ / 引用 | 类

引用本作用： 给变量起别名语法： 数据类型 & 别名原名； 应用代码 #include <iostream>using namespace std;int main() {int a 10;int& b a;b 100;cout << "a " << a << endl;cout <…...

编程日记 2025/6/29 12:27:54

在任意路径下简单开启jupyter notebook

正常的开启方式为： 安装anaconda, 在anaconda界面开启jupyter. 但是启动后root的路径不好改变。可以直接通过cmd方式打开jupyter. cd D: # cd到d盘 jupyter notebook # 启动此时开启jupyter notebook, root为D盘路径。按此方式可以在任意路径启动jupyter noteb…...

编程日记 2025/7/19 21:12:50

2025年阿里云云计算ACP高级工程师认证模拟试题（附答案解析）

这篇文章的内容是阿里云云计算ACP高级工程师认证考试的模拟试题。所有模拟试题由AI自动生成，主要为了练习和巩固知识，并非所谓的 “题库”，考试中如果出现同样试题那真是纯属巧合。 1、设计云上架构时，如果能充分了解云服务的特…...

编程日记 2025/6/29 11:19:41

锂电池4.2V升压24V推荐哪些升压芯片?高效率国产SL4013输入耐压2.7V-25V

SL4013作为一款高性能升压型DC-DC转换芯片，在单节锂电池（4.2V）升压至24V的应用中展现出以下核心优势： 一、宽输入电压适应性 SL4013支持2.7V-25V的输入范围，尤其适合单节锂电池（3.7V-4.2V）的宽…...

编程日记 2025/7/19 20:03:37

中电金信联合阿里云推出智能陪练Agent

在金融业加速数智化转型的今天，提升服务效率与改善用户体验已成为行业升级的核心方向。面对这一趋势，智能体与智能陪练的结合应用，正帮助金融机构突破传统业务模式，开拓更具竞争力的创新机遇。在近日召开的阿里云AI势能大会期间&…...

编程日记 2025/7/16 1:39:09

基于扣子（Coze.cn）与火山引擎构建高性能智能体的实践指南

1. 引言 1.1. 背景与目标人工智能（AI）智能体（Agent）平台的兴起，例如扣子（Coze），正显著改变我们构建复杂 AI 应用的方式 1。这些平台旨在降低技术门槛，让不同技能水平的…...

编程日记 2025/6/29 9:37:53

w~视觉~3D~合集2

我自己的原文哦~ https://blog.51cto.com/whaosoft/13766161 #Sin3DGen 最近有点忙可能给忘了,贴了我只是搬运工发这些给自己看, 还有下面不是隐藏是发布出去 ~ 北京大学xxx团队联合山东大学和xxx AI Lab的研究人员，提出了首个基于单样例场景无需训练便可生…...

编程日记 2025/7/7 3:27:02

SAS宏核心知识与实战应用

1. SAS宏基础 1.1 核心概念 1.1.1 宏处理器宏处理器在SAS程序运行前执行，用于生成动态代码，可实现代码的灵活定制。通过宏处理器，可基于输入参数动态生成不同的SAS代码，提高代码复用性。 1.1.2 宏变量宏变量是存储文本值的容器，用&符号引用，如&var，用于存储…...

编程日记 2025/6/29 11:45:26

windows使用openssl生成IIS自签证书全流程

使用 OpenSSL 生成适用于 IIS 的证书，通常需要经过以下步骤：生成私钥、生成证书签名请求（CSR）、生成自签名证书或通过 CA 签名，最后将证书转换为 IIS 所需的 PFX 格式。以下是详细步骤： 1. 安装 OpenSSL …...

编程日记 2025/6/29 11:47:12

笔记本电脑研发笔记：BIOS，Driver，Preloader详记

在笔记本电脑的研发过程中，Driver（驱动程序）、BIOS（基本输入输出系统）和 Preloader（预加载程序）之间存在着密切的相互关系和影响，具体如下： 相互关系 BIOS 与 Preload…...

编程日记 2025/7/14 11:40:02

鸿蒙生态：鸿蒙生态校园行心得

（个人观点，仅供参考） 兄弟们，今天来浅浅聊一聊这次的设立在长沙的鸿蒙生态行活动。老样子，我们先来了解一下这个活动： Ｈａｒｍｏｎ&#x…...

编程日记 2025/6/29 9:37:33

云原生周刊：KubeSphere 平滑升级

开源项目推荐 Kagent Kagent 是一个开源的 K8s 原生框架，旨在帮助 DevOps 和平台工程师在 K8s 环境中构建和运行 AI 代理（Agentic AI）。与传统的生成式 AI 工具不同，Kagent 强调自主推理和多步骤任务的自动化执行，适…...

编程日记 2025/6/29 11:31:48

Uniapp：swiper(滑块视图容器)

目录一、基本概述二、属性说明三、基本使用一、基本概述一般用于左右滑动或上下滑动，比如banner轮播图二、属性说明属性名类型默认值说明平台差异说明indicator-dotsBooleanfalse是否显示面板指示点indicator-colorColorrgba(0, 0, 0, .3)指示点颜色indicat…...

编程日记 2025/6/29 12:11:40

开源的自动驾驶模拟器

以下是目前主流的 ‌开源自动驾驶模拟器‌，适用于算法开发、测试和研究： ‌1. CARLA‌ ‌官网/GitHub‌: carla.org | GitHub‌许可证‌: MIT‌特点‌: 基于虚幻引擎（Unreal Engine），提供高保真城市场景（支…...

编程日记 2025/7/19 0:38:08

Uniapp：scroll-view(区域滑动视图)

目录一、基本概述二、属性说明三、基本使用3.1 纵向滚动3.2 横向滚动一、基本概述 scroll-view，可滚动视图区域。用于区域滚动。二、属性说明属性名类型默认值说明平台差异说明scroll-xBooleanfalse允许横向滚动scroll-yBooleanfalse允许纵向滚动三、基本使…...

编程日记 2025/6/29 9:37:28

【漏洞复现】Struts2系列

【漏洞复现】Struts2系列 1. 了解Struts21. Struts2 S2-061 RCE （CVE-2020-17530）1. 漏洞描述2. 影响版本3. 复现过程 1. 了解Struts2 Apache Struts2是一个基于MVC设计模式的Web应用框架，会对某些标签属性（比如 id）的…...

编程日记 2025/7/19 20:40:45

洗车小程序系统前端uniapp 后台thinkphp

洗车小程序系统前端uniapp 后台thinkphp 支持多门店分销在线预约套餐卡等...

编程日记 2025/7/16 10:15:56

【RuleUtil】适用于全业务场景的规则匹配快速开发工具

一、RuleUtil 开发背景 1.1 越来越多，越来越复杂的业务规则 1、规则的应用场景多 2、规则配置的参数类型多（ID、数值、文本、日期等等） 3、规则的参数条件多（大于、小于、等于、包含、不包含、区间等等） 4、规则的结…...

编程日记 2025/7/15 20:38:12

多表查询之嵌套查询

目录引言一、标量嵌套查询二、列嵌套查询三、行嵌套查询四、表嵌套查询引言 1、概念 SQL语句中嵌套 select 语句，称为嵌套查询，又称子查询。嵌套查询外部的语句可以是 insert / update / delete / select 的任何一个。嵌套…...

编程日记 2025/7/17 19:29:35

js原型链prototype解释

function Person(){} var personnew Person() console.log(啊啊,Person instanceof Function);//true console.log(,Person.__proto__Function.prototype);//true console.log(,Person.prototype.__proto__ Object.prototype);//true console.log(,Function.prototype.__prot…...

编程日记 2025/6/29 11:54:32

文章目录

1. 图的基本概念

2. 图的一些现实的应用

2.1 ABCDE各个城市之间的关系

2.2 社交关系

3. 图的存储结构

3.1邻接矩阵

3.2 邻接矩阵的实现

3.3 邻接表

相关文章：