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

算法初学者（图的存储）链式前向星

news 来源：原创 2025/6/18 4:38:08

知识储备：概念，存储，遍历，最短路，最小生成树，拓扑排序-关键路径

图的存储：邻接矩阵，邻接表，十字链表，多重邻接表，边集数组

其中：邻接表，十字链表，多重邻接表是基于链表实现的，涉及到指针，代码操作复杂，且容易出现空指针，野指针的bug。

其中，刷题时常用的是邻接矩阵和邻接表，但是因为上述原因，需要对邻接表的代码实现改进。

邻接矩阵和边集数组是基于数组的，按照上一篇讲解实现即可。

邻接表：一维数组存点---顶点数组。每个顶点的所有邻接点构成一个链表，挂在顶点数组后。

邻接表存无权图，可以直接将邻接表转化成二维数组，a[x][i]=y;顶点x的第i个邻接点是顶点y，即顶点x的第i条出边是边<x,y>。注意和邻接矩阵的区分。

不带权的邻接表转换为二维数组并且深度优先遍历代码如下

#include<iostream>
#include<vector>
using namespace std;
vector<vector<int>>adj;
int n, m;//n个点，m条边
int v[105];
void DFS(int u) {if (v[u] == 1)return;printf("%d ", u);v[u] = 1;for (int i = 0; i < adj[u].size(); i++) {int v1 = adj[u][i];if (v[v1] == 0) {DFS(v1);}}
}
int main() {int x, y;scanf("%d %d", &n, &m);adj.resize(n + 1);for (int i = 1; i <= m; i++) {scanf("%d %d", &x, &y);adj[x].push_back(y);//把y加到x那行adj[y].push_back(x);//把x加到y那行}for (int i = 1; i <= n; i++) {if (v[i] == 0) {DFS(i);}}return 0;
}
//4 5
//1 2
//1 4
//2 3
//2 4
//3 4

带权的邻接表转换为二维数组代码如下（静态链表）（边集数组）----链式前向星

链式前向星的两种结构

1边集数组：edge[],edge[i]表示第i条边，存储边的信息：to,w,next,其中next不再是指针而是边的编号。

2头节点数组：head[],head[x]存以x为起点的第一条边的下标指：在edge[]中的下标。初始时head[]数组全部初始化为-1，即认为没有边。

#include<iostream>
#include<vector>
using namespace std;
struct Edge {int to;//终点int w;//边权int next;//具有相同起点的下一条边
}e[10005];
int head[105];
int n, m;//n点 m边
int cut;//实际边的数目，边的编号
void add(int x, int y, int w) {e[cut].to = x;e[cut].w = w;e[cut].next = head[x];head[x] = cut;cut++;//为下一条边
}
int v[105];//用来记录有没有被遍历过
void DFS(int x) {if (v[x] == 1)return;printf("%d ", x);v[x] = 1;for (int i = head[x]; i != -1; i = e[i].next) {//i是边的编号,y才是终点（他的邻接点）--接下来遍历邻接点int y = e[i].to;if (v[y] == 0) {DFS(y);}}
}
int main() {int x, y, w;scanf("%d %d", &n, &m);memset(head, -1, sizeof(head));cut = 0;for (int i = 0; i < m; i++) {scanf("%d %d %d", &x, &y, &w);add(x, y, w);add(y, x, w);//无向图建边}for (int i = 1; i <= n; i++) {if (v[i] == 0) {DFS(i);}}return 0;
}
//4 5
//1 2 5
//1 4 3
//2 3 8
//2 4 12
//3 4 9

结构体数组可以分解成三个数组

链式前向星DFS遍历时间复杂度（v+e）--点+边

算法初学者（图的存储）链式前向星

知识储备：概念，存储，遍历，最短路，最小生成树，拓扑排序-关键路径图的存储：邻接矩阵，邻接表，十字链表，多重邻接表，边集数组其中：邻接…...

编程日记 2025/6/4 5:57:29

Github 2025-01-11 Rust开源项目日报 Top10

根据Github Trendings的统计，今日(2025-01-11统计)共有10个项目上榜。根据开发语言中项目的数量，汇总情况如下：开发语言项目数量Rust项目10C项目1Swift项目1Yazi - 快速终端文件管理器创建周期：210 天开发语言：Rust协议类型：MIT LicenseStar数量：5668 个Fork数量：122…...

编程日记 2025/6/4 16:48:02

Leetcode 3419. Minimize the Maximum Edge Weight of Graph

Leetcode 3419. Minimize the Maximum Edge Weight of Graph 1. 解题思路2. 代码实现3. 算法优化题目链接：3419. Minimize the Maximum Edge Weight of Graph 1. 解题思路这一题我的思路就是二分法，找到能够完成遍历的临界值即可。但是自己实际在…...

编程日记 2025/6/3 11:23:48

深入理解数据库索引及其优化策略

数据库作为现代应用系统的核心组件之一，如何高效地存储和检索数据成为开发者关注的焦点。在处理大规模数据时，数据库索引是提升查询性能的关键技术之一。本文将深入探讨数据库索引的工作原理、常见类型、创建索引的策略以及如何优化索引，以…...

编程日记 2025/5/29 22:16:35

安科瑞 Acrel-1000DP 分布式光伏监控系统在工业厂房分布式光伏发电项目中的应用

吕梦怡 18706162527 摘要：常规能源以煤、石油、天然气为主，不仅资源有限，而且会造成严重的大气污染，开发清洁的可再生能源已经成为当今发展的重要任务，“节能优先，效率为本”的分布式发电能源符合社会发…...

编程日记 2025/6/3 5:55:30

css面试常考布局（圣杯布局、双飞翼布局、三栏布局、两栏布局、三角形）

两栏布局 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, initial-scale1.0"><title>Document</title> </head> &…...

编程日记 2025/5/30 22:03:41

【物流管理系统 - IDEAJavaSwingMySQL】基于Java实现的物流管理系统导入IDEA教程

有问题请留言或私信步骤下载项目源码：项目源码解压项目源码到本地打开IDEA 左上角：文件 → 新建 → 来自现有源代码的项目找到解压在本地的项目源代码文件，点击确定，根据图示步骤继续导入项目查看项目目录&#xff…...

编程日记 2025/5/31 10:27:59

IntelliJ IDEA 主题插件

在 IntelliJ IDEA 中，有很多优秀的主题插件可以帮助你改变 IDE 的外观和配色方案，使得开发过程更加愉悦和高效。以下是一些非常受欢迎和实用的主题插件，以及如何安装和使用它们的步骤： 🌟 流行主题插件推荐 1️⃣ Ma…...

编程日记 2025/6/2 10:39:35

ASP.NET Core 中，Cookie 认证在集群环境下的应用

在 ASP.NET Core 中，Cookie 认证在集群环境下的应用通常会遇到一些挑战。主要的问题是 Cookie 存储在客户端的浏览器中，而认证信息（比如 Session 或身份令牌）通常是保存在 Cookie 中，多个应用实例需要共享这些 Cookie …...

编程日记 2025/6/3 10:38:04

k8s笔记29--使用kyverno提高运维效率

k8s笔记29--使用kyverno提高运维效率介绍原理安装应用场景自动修正测试环境pod资源强制 Pod 标签限制容器镜像来源禁止特权容器其它潜在场景注意事项说明介绍 Kyverno是一个云原生的策略引擎，它最初是为k8s构建的，现在也可以在k8s集群之外用作统一的…...

编程日记 2025/5/28 20:41:02

快速上手Git——Windows系统下Git的安装与简单使用流程

一、Git的下载和安装 Git官网链接：https://git-scm.com/ 进入官网后选择Downloads 选择与系统相符合的版本下载，这里我使用的是windows系统然后点击下载根据流程安装完成后，使用以下命令查看git版本 git -v运行结果： 二、…...

编程日记 2025/6/4 14:57:58

apollo内置eureka dashboard授权登录

要确保访问Eureka Server时要求输入账户和密码，需要确保以下几点： 确保 eurekaSecurityEnabled 配置为 true：这个配置项控制是否启用Eureka的安全认证。如果它被设置为 false，即使配置了用户名和密码，也不会启用安全认…...

编程日记 2025/6/4 1:20:52

linux--防火墙 iptables 双网卡 NAT 桥接

linux--防火墙 iptables 双网卡 NAT 桥接 1 介绍1.1 概述1.2 iptables 的结构 2 四表五链2.1 iptables 的四表filter 表：过滤规则表，默认表。nat 表：地址转换表。mangle 表：修改数据包内容。raw 表：原始数据包表。 2.2…...

编程日记 2025/6/4 10:48:21

C#反射的应用案例与讲解

C# 反射文章目录 C# 反射前言案例展示将对象转为字典测试用例执行效果代码讲解 HasValue扩展测试用例执行效果代码讲解反射的底层逻辑反射的原理反射的基本概念反射常用的API和方法GetType类Activator类PropertyInfo类EventInfo 类MemberInfo类MethodInfo类反射的优缺点优点…...

编程日记 2025/6/2 23:41:52

Mysql常见知识点

Mysql是最常用的数据库了。 1、什么是关系型数据库？ 关系型数据库（RDB，Relational Database）就是一种建立在关系模型的基础上的数据库。关系模型表明了数据库中所存储的数据之间的联系（一对一、一对多、多对多&#…...

编程日记 2025/6/4 14:27:45

玩转 JMeter：Random Order Controller让测试“乱”出花样

嘿，各位性能测试的小伙伴们！今天咱要来唠唠 JMeter 里超级有趣又超实用的 Random Order Controller（随机顺序控制器），它就像是性能测试这场大戏里的“魔术棒”，轻轻一挥，就能让测试场景变得千变…...

编程日记 2025/5/28 10:17:16

企业级PHP异步RabbitMQ协程版客户端 2.0 正式发布

概述 workerman/rabbitmq 是一个异步RabbitMQ客户端，使用AMQP协议。 RabbitMQ是一个基于AMQP（高级消息队列协议）实现的开源消息组件，它主要用于在分布式系统中存储和转发消息。RabbitMQ由高性能、高可用以及高扩展性出名的Erlan…...

编程日记 2025/5/29 14:50:45

计算机网络（37）TCP的流量控制

前言计算机网络中的TCP（传输控制协议）流量控制是一种重要机制，用于确保数据在发送方和接收方之间的传输既高效又稳定。一、目的 TCP流量控制的主要目的是防止发送方发送数据过快，导致接收方无法及时处理，从而引起数据…...

编程日记 2025/6/1 10:45:59

Windows10下安装vue2.0项目所需环境

一、Node.js版本管理器NVM安装 1.下载NVM安装包 nvm全英文也叫node.js version management，是一个nodejs的版本管理工具。nvm和n都是node.js版本管理工具，为了解决node.js各种版本存在不兼容现象可以通过它可以安装和切换不同版本的node.js。目前最新版…...

编程日记 2025/5/29 21:41:02

使用Cilium/eBPF实现大规模云原生网络和安全

大家读完觉得有帮助记得关注和点赞！！！ 目录抽象 1 Trip.com 云基础设施 1.1 分层架构 1.2 更多细节 2 纤毛在 Trip.com 2.1 推出时间表 2.2 自定义 2.3 优化和调整 2.3.1 解耦安装 2.3.2 避免重试/重启风暴 2.3.3 稳定性优先 2…...

编程日记 2025/6/1 10:32:08

文章目录 1.目录2.代码 1.目录 2.代码 package com.sunxiansheng.mybatis.plus.inteceptor;import org.apache.ibatis.executor.statement.StatementHandler; import org.apache.ibatis.mapping.*; import org.apache.ibatis.plugin.*; import org.apache.ibatis.reflection.*…...

编程日记 2025/6/4 4:08:30

网络基础1 http1.0 1.1 http/2的演进史

http1.0 1.1 http/2的演进史😎 （连接复用队头阻塞服务器推送 2进制分帧） 概述我们主要关注的是应用层传输层 http协议发展历史 http的报文结构：起始行 Header Body http的典型特征 http存在的典型问题 Keep Alive机制 chun…...

编程日记 2025/6/4 13:54:21

MySQL不使用子查询的原因

MySQL不使用子查询的原因及优化案例目录 MySQL不使用子查询的原因及优化案例目录不推荐使用子查询和JOIN的原因解决方案优化案例案例1：查询所有有库存的商品信息案例2：使用EXISTS优化子查询案例3：使用JOIN代替子查询案例4：优化…...

编程日记 2025/5/30 10:39:09

网络编程（1）

网络编程概述 Java是 Internet 上的语言，它从语言级上提供了对网络应用程序的支持，程序员能够很容易开发常见的网络应用程序。 Java提供的网络类库，可以实现无痛的网络连接，联网的底层细节被隐藏在 Java 的本机安装系统里&#…...

编程日记 2025/6/3 1:23:15

Jaeger UI使用、采集应用API排除特定路径

Jaeger使用注： Jaeger服务端版本为：jaegertracing/all-in-one-1.6.0 OpenTracing版本为：0.33.0，最后一个版本，停留在May 06, 2019。最好升级到OpenTelemetry。 Jaeger客户端版本为：jaeger-client-1.3.2。…...

编程日记 2025/6/3 8:14:43

【python:文件-＞统计飞鸟集单词个数】

主函数.py fopen("飞鸟集.txt",r,encoding"UTF-8")#只读方式打开 contentf.read()# 提取全文,将文件内容字符串对象返回给content dccontent.split("\n")#对字符串调用分割符切割 print(dc) f.close() # 统计单词频率 ofnumcontent.count("…...

编程日记 2025/5/30 5:02:06

解决SpringBoot无法使用JDK8问题

解决SpringBoot无法使用JDK8问题现状解决方案现状使用idea创建springboot项目无法选择java8。原因是23年11月的spring更新后就明确了不在支持java8版本的项目创建，但是目前为止很多公司开发还在用java8，导致会有问题的产生。解决方案使用idea创…...

编程日记 2025/5/27 1:12:38

论文导读 | 数据库系统中基于机器学习的基数估计方法

背景基数估计任务是在一个查询执行之前预测其基数，基于代价的查询优化器（Cost Based Optimizer）将枚举所有可能的执行计划，并利用估计的基数选出期望执行代价最小的计划，从而完成查询优化的任务。然而，…...

编程日记 2025/6/3 23:23:22

Shader-＞LinearGradient线性渐变着色器详解

XML文件 <com.example.myapplication.MyViewxmlns:android"http://schemas.android.com/apk/res/android"android:layout_width"match_parent"android:layout_gravity"center"android:layout_height"400dp"/>自定义View代码 c…...

编程日记 2025/6/3 16:33:05

Unity打包+摄像机组件

转换场景使用程序集：using UnityEngine.SceneManagement; 切换场景相关代码：SceneManager.LoadScene(1);//括号内可放入场景名称，场景索引等 //Application.LoadLevel(""); 老版本Unity加载场景方法打包相关 Bundle Identi…...

编程日记 2025/6/3 6:30:28

Git 命令代码管理详解

一、Git 初相识：版本控制的神器在当今的软件开发领域，版本控制如同基石般重要，而 Git 无疑是其中最耀眼的明珠。它由 Linus Torvalds 在 2005 年创造，最初是为了更好地管理 Linux 内核源代码。随着时间的推移，Git 凭借…...

编程日记 2025/5/31 18:26:11

游戏引擎学习第78天

Blackboard: Position ! Collision “网格” 昨天想到的一个点，可能本来就应该想到，但有时反而不立即思考这些问题也能带来一些好处。节目是周期性的，每天不需要全程关注，通常只是在晚上思考，因此有时我们可能不能那么…...

编程日记 2025/6/3 15:00:33

Centos9-SSH免密登录配置-修改22端口-关闭密码登录-提高安全性

Centos9-SSH免密登录配置-修改22端口-关闭密码登录生成秘钥对将公钥信息存进authorized_keys测试登录查询访问记录、比对指纹更换22访问端口关闭账号密码登录生成秘钥对生成密钥对，指定备注和文件目录命令执行后，默认两次回车，不设置秘钥使用密码ssh-keygen -t rsa -b …...

编程日记 2025/5/29 23:11:12

汇总统计数据--SQL中聚集函数的使用

目录 1、为什么需要汇总数据 2、聚集函数 （1）AVG函数 （2）COUNT函数 （3）MAX和MIN函数 （4）SUM函数 3、聚集不同值--DISTINCT 4、组合聚集函数 5、小结博主用的是mysql8 DBMS…...

编程日记 2025/6/3 10:36:50

pdf提取文本，表格以及转图片：spire.pdf

文章目录 🐒个人主页：信计2102罗铠威🏅JavaEE系列专栏📖前言：🎀 1. pdfbox1.1导入pdfbox 的maven依赖1.1 提取文本1.2 提取文本表格（可自行加入逻辑处理）1.3 pdf转换成图片代码&…...

编程日记 2025/6/2 2:12:19

【C#学习笔记】C#中委托

概述 C#的委托是一种类型安全的函数指针，用于引用方法，委托允许方法作为参数传递，或者将方法赋值给委托变量，并通过委托调用方法。委托类型：委托定义了方法的的签名（[方法的参数类型和返回值]&#xff0…...

编程日记 2025/6/4 14:29:07

C#的Task

优先使用Task.Run，除非有定制化需求才用Task.Factory.StartNew Task.Factory.StartNew的TaskScheduler参数颠覆你的认知： var cnt 0;var cancelToken new CancellationTokenSource();await Task.Factory.StartNew(() > {cnt;Debug.WriteLine($&quo…...

编程日记 2025/6/3 10:07:05

企业全文搜索-搜索权限，非侵入文档同步，权限同步，扩展字段

简介企业全文搜索帮助员工高效快速定位所需的信息和资源，搜索权限控制是必须的，原因有二，首先，企业文档，包括公文，流程，技术文档等，带有敏感信息，搜索返回带片段，可能带出敏感信息；其次，若没有权限，用户搜索出来的文档可能不能阅读原文，体验非常差。onesearch有…...

编程日记 2025/5/31 15:04:34

Linux电源管理——CPUidle Framework

目录前言一、CPU idle 二、cpuidle framework 相关概念三、cpuidle core 数据结构 3.1、cpuidle_state 3.2、cpuidle_driver 3.3、cpuidle_device 3.4、cpuidle_governor 四、cpuidle driver初始化流程 4.1、cpuidle driver 初始化方式 4.2、drv->states[0]的初…...

编程日记 2025/6/3 22:47:58

【黑灰产】假钱包推广套路

假钱包推广产业链研究市面上钱包的主要推广方式： 1，竞价（搜索引擎），误导客户为真正官方钱包从而完成下载使用优点：精准，客户大缺点：竞价户容易挂，投资大 2&#xff0…...

编程日记 2025/5/28 3:12:57

联想java开发面试题及参考答案

IP 协议是哪一层的？ IP 协议（Internet Protocol）属于网络层协议。网络层主要负责将数据从源节点传输到目标节点，它在整个网络通信体系中起到了承上启下的关键作用。在分层网络模型中，下层（如数据链路层）为网络层提供物理链路的连接和帧传输服务。数据链路层关注的是在相…...

编程日记 2025/6/2 19:15:07

C# 继承(接口)

接口如果一个类派生与一个接口，它就会执行某些函数。并不是所有的面向对象语言都支持接口。熟悉COM的开发人员应注意，尽管在概念上C#接口类似于COM接口，但他们是不筒的，底层的结构不筒。比如，C#接口并不派生于IUnko…...

编程日记 2025/5/31 14:49:20

FPGA的基本结构（Xilinx 公司Virtex-II 系列FPGA ）

以Xilinx 公司Virtex-II 系列FPGA 为例，其基本结构由下图所示。它是主要由两大部分组成：可编程输入/输出（Programmable I/Os）部分和内部可配置（Configurable Logic）部分。可编程输入/输出（I/Os…...

编程日记 2025/5/31 1:03:56

妙用编辑器：把EverEdit打造成一个编程学习小环境

1 妙用编辑器：把EverEdit打造成一个编程学习小环境 1.1 应用场景最近在学习Python语言，由于只是学习和练习，代码规模很小，不想惊动PyCharm、VSCode、WingIDE这些重型武器，只想轻快的敲些代码，记事本虽好&…...

编程日记 2025/6/3 10:19:46

ELK日志分析实战宝典之ElasticSearch从入门到服务器部署与应用

目录 ELK工作原理展示图一、ElasticSearch介绍（数据搜索和分析） 1.1、特点 1.2、数据组织方式 1.3、特点和优势 1.3.1、分布式架构 1.3.2、强大的搜索功能 1.3.3、数据处理与分析 1.3.4、多数据类型支持 1.3.5、易用性与生态系统 1.3.6、高性…...

编程日记 2025/6/2 20:34:46

【学习笔记】理解深度学习和机器学习的数学基础：数值计算

深度学习作为人工智能领域的一个重要分支，其算法的实现和优化离不开数值计算。数值计算在深度学习中扮演着至关重要的角色，它涉及到如何在计算机上高效、准确地解决数学问题。本文将介绍深度学习中数值计算的一些关键概念和挑战，以及如何应对…...

编程日记 2025/6/3 19:56:32

【Java回顾】Day5 并发基础|并发关键字|JUC全局观|JUC原子类

JUC全称java.util.concurrent 处理并发的工具包(线程管理、同步、协调) 一.并发基础多线程要解决什么问题？本质是什么？ CPU、内存、I/O的速度是有极大差异的，为了合理利用CPU的高性能，平衡三者的速度差异，解决办法…...

编程日记 2025/6/3 6:41:02

VSCODE使用Echarts组件库(不是vue)

第一步打开Echarts官网 Examples - Apache ECharts 第二步随便点击一个图形点击我圈的按钮第三步...

编程日记 2025/5/15 19:21:10

DNS解析域名简记

域名通常是由: 权威域名.顶级域名.根域名组成的。从左往右，级别依次升高，这和外国人从小范围到大范围的说话习惯相关。（我们自己是更习惯先说大范围再说小范围，如XX省XX市XX区XX路） DNS解析域名时，会先查…...

编程日记 2025/6/3 2:11:47

选择器css

1.a标签选择 // 选中所具有herf 的元素 [herf] {color: skyblue; } // 选中所具有herfhttps://fanyi.youdao.com/ 的元素 [herf$"youdao.com"] {color:pink; } // 按此顺序书写 link visited hover active // 未访问状态 a:link {color:orange } // 访问状态 a…...

编程日记 2025/5/28 23:00:45

相关文章：