【图论】详解链式前向星存图法+遍历法

细说链式前向星存图法

首先要明白,链式前向星的原理是利用存边来进行模拟图。

推荐左神的视频–建图、链式前向星、拓扑排序

在这里插入图片描述

比方说有这样一张图,我们用链式前向星来进行模拟时,可以将每一条边都进行编号,其中,红色的数字就是对每一条边的编号蓝色的数字表示每一个结点编号

准备三个数组head[], next[], to[]

数组名称下标含义值的含义
head结点值结点指向的边
next边的编号该边指向下一条边
to边的编号边指向的结点值

idx:表示当前还没有分配的边编号

添加边

所以添加边的函数add()可以这样去设计:

//建立一个a->b的结点->结点,->表示边
inline void add(int a, int b) {
	to[idx] = b, next[idx] = head[a], head[a] = idx++;
}
//新建一条边,编号为idx,指向结点b,然后在a结点的邻居边中增加idx边,思想类似与头插法,让这个新的边指向头边,并修改头边为新的边。

Code

#include <iostream>
#include <cstring>
using namespace std;

const int N = 10001;				//最多生成N个结点,N-1个单边
int head[N], to[N], next[N], idx;

// head[]头边号 
// 点号 

// next[] 下一条边号 
// 边号

// to[] 去往的点
// 边号

// idx 
inline void add(int a, int b) {
	to[idx] = b, next[idx] = head[a], head[a] = idx++;
}

inline void dfs(int u) {
	cout << u << ' ';
	int i = head[u];		//i为u结点第一条边
	for (; i != -1; i = next[i]) {
		//每次更新为下一条边
		dfs(to[i]); 		//去到 i 边指向的结点 
	}
}

int main() {
	memset(head, -1, sizeof head);//head[i]为-1表示这个结点没有后继边
	add(1, 2);
	add(1, 5);
	add(1, 6);
	add(2, 6);
	add(5, 6);
	dfs(1);
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/532582.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

SQL注入sqli_labs靶场第五、六题

第五题 根据报错信息&#xff0c;判断为单引号注入 没有发现回显点 方法&#xff1a;布尔盲注&#xff08;太耗时&#xff0c;不推荐使用&#xff09; 1&#xff09;猜解数据库名字&#xff1a;&#xff08;所有ASCII码值范围&#xff1a;0~127&#xff09; ?id1 and length…

数字化浪潮下,制造业如何乘势而上实现精益生产

随着数字化技术的迅猛发展&#xff0c;制造业正迎来前所未有的变革机遇。本文将探讨如何利用数字化手段助推制造业实现精益生产&#xff0c;从而在激烈的市场竞争中脱颖而出。 1、构建智能化生产系统 借助物联网技术&#xff0c;实现设备之间的互联互通&#xff0c;构建智能化…

【Qt踩坑】ARM 编译Qt5.14.2源码-QtWebEngine

1.下载源码 下载网站&#xff1a;Index of /new_archive/qt/5.14/5.14.2/single 2.QWebEngine相关依赖 sudo apt-get install flex libicu-dev libxslt-dev sudo apt-get install libssl-dev libxcursor-dev libxcomposite-dev libxdamage-dev libxrandr-dev sudo apt-get …

3. Spring 注解存储对象 Bean的命名规范

从Java5.0开始&#xff0c;Java开始支持注解。Spring做为Java生态中的领军框架&#xff0c;从2.5版本后也开始支持注解。相比起之前使用xml来配置Spring框架&#xff0c;使用注解提供了更多的控制Spring框架的方式。 SpringFramework版本对应jdk版本重要特性SpringFramework 1…

Linux——fork复制进程

1)shell: 在计算机科学中&#xff0c;Shell俗称壳&#xff08;用来区别于核&#xff09;&#xff0c;是指“为使用者提供操作界面”的软件&#xff08;command interpreter&#xff0c;命令解析器&#xff09;。它类似于DOS下的COMMAND.COM和后来的cmd.exe。它接收用户命令&…

练习题(2024/4/10)

1. 删除有序数组中的重复项 给你一个 非严格递增排列 的数组 nums &#xff0c;请你 原地 删除重复出现的元素&#xff0c;使每个元素 只出现一次 &#xff0c;返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。 考虑 nums 的唯一元…

安装VMware ESXi虚拟机系统

简介&#xff1a;ESXi是VMware公司开发的一款服务器虚拟化操作系统。它能够在一台物理服务器上运行多个虚拟机&#xff0c;每个虚拟机都可以独立运行操作系统和应用程序&#xff0c;而且对硬件配置要求低&#xff0c;系统运行稳定。 准备工具&#xff1a; 1.8G或者8G以上容…

查看TensorFlow已训模型的结构和网络参数

文章目录 概要流程 概要 通过以下实例&#xff0c;你将学会如何查看神经网络结构并打印出训练参数。 流程 准备一个简易的二分类数据集&#xff0c;并编写一个单层的神经网络 train_data np.array([[1, 2, 3, 4, 5], [7, 7, 2, 4, 10], [1, 9, 3, 6, 5], [6, 7, 8, 9, 10]]…

MySQL高级(索引结构Hash,为什么InnoDB存储引擎选择使用B+tree索引结构?)

目录 1、Hash索引结构 2、Hash索引特点 3、存储引擎支持 4、为什么InnoDB存储引擎选择使用Btree索引结构&#xff1f; 1、Hash索引结构 哈希索引就是采用一定的hash算法&#xff0c;将键值换算成新的hash值&#xff0c;映射到对应的槽位上&#xff0c;然后存储在hash表中。 如…

吴恩达机器学习-异常检测(Anomaly Detection)

在本练习中&#xff0c;您将实现异常检测算法&#xff0c;并将其应用于检测网络上出现故障的服务器。 文章目录 1-包2-异常检测2.1问题陈述2.2数据集2.3高斯分布2.2.1高斯实现的估计参数&#xff1a;2.2.2选择阈值&#x1d716; 2.4高维数据集 1-包 首先&#xff0c;让我们运…

脑电放大 LM386

LM386介绍 LM386 是一种音频集成功放&#xff0c;具有自身功耗低、电压增益可调整电源电压范围大、外接元件少和总谐波失真小等优点&#xff0c;广泛应用于录音机和收音机之中。 电源电压 4-12V 或 5-18V(LM386N-4);静态消耗电流为 4mA;电压增益为20-200dB;在引脚1和8开路时&a…

Android开发基础:事件传递 基于监听器的事件处理 基于回调的事件处理

目录 一&#xff0c;事件传递机制 1.事件传递机制的三个方法 &#xff08;1&#xff09;public boolean dispatchTouchEvent&#xff08;MotionEvent event&#xff09; &#xff08;2&#xff09;public boolean onInterceptTouchEvent&#xff08;MotionEvent event&…

【C++题解】1601. 挖胡萝卜

问题&#xff1a;1601. 挖胡萝卜 类型&#xff1a;基本运算、小数运算 题目描述&#xff1a; 小兔朱迪挖了 x 个胡萝卜&#xff0c;狐狸尼克挖到胡萝卜数量是小兔挖到的 3 倍&#xff0c;小羊肖恩挖到胡萝卜的数量比狐狸尼克少 8 个。 请你编程计算一下狐狸尼克和小羊肖恩分别…

时间系列预测总结

转载自&#xff1a;https://mp.weixin.qq.com/s/B1eh4IcHTnEdv2y0l4MCog 拥有一种可靠的方法来预测和预测未来事件一直是人类的愿望。在数字时代&#xff0c;我们拥有丰富的信息&#xff0c;尤其是时间序列数据。 时间序列是指基于时间刻度维度&#xff08;天、月、年等&…

Mybatis plus 使用通用枚举

说明&#xff1a;mybatis plus 使用枚举可实现数据库存入时指定值保存&#xff0c; 读取时指定值展示&#xff08;返给前端&#xff09; 可通过继承IEnum<T>、 EnumValue实现 1、引包 <dependency><groupId>mysql</groupId><artifactId>mysql-…

java基础语法(16)| 集合

前言 Hello,大家好!很开心与你们在这里相遇,我是一个喜欢文字、喜欢有趣的灵魂、喜欢探索一切有趣事物的女孩,想与你们共同学习、探索关于IT的相关知识,希望我们可以一路陪伴~ 1. 集合概述 什么是集合 集合:集合是java中提供的一种容器,可以用来存储多个数据,并且可以存…

每天五分钟深度学习PyTorch:面对Tensorflow,为何我选择PyTorch

这篇专栏文章不是为了挑起tenserflow和pytorch中哪个更好&#xff0c;众所周知tensorflow诞生以来&#xff0c;已经成为最流行的深度学习框架&#xff0c;可以说github中大多数的深度学习代码实现是以tensorflow实现的&#xff0c;也就是说资源众多&#xff0c;社区强大&#x…

自动化测试十大必备(背)面试题!【含答案精讲】

&#x1f525; 交流讨论&#xff1a;欢迎加入我们一起学习&#xff01; &#x1f525; 资源分享&#xff1a;耗时200小时精选的「软件测试」资料包 &#x1f525; 教程推荐&#xff1a;火遍全网的《软件测试》教程 &#x1f4e2;欢迎点赞 &#x1f44d; 收藏 ⭐留言 &#x1…

OJ 最大奖励 C Python【贪心算法】【动态规划】

又接触到贪心算法啦&#xff0c;这道题有两种算法思路&#xff0c;我用两个语言来写了一下&#xff0c;这也涉及到了一些动态规划的思路 一.从最后一个时间枚举&#xff0c;找到在这个时间内可以完成的最大分值的题 注意点&#xff1a; 1.数组下标从1开始记录表示第几个时间…

渲染农场实时画面怎么设置?云渲染农场实时预览效果查看

许多用户在使用渲染农场服务时&#xff0c;常常难以找到查看实时渲染画面的功能。由于渲染是一个时间消耗较大的任务&#xff0c;如果最终结果与预期不符&#xff0c;可能会对整个工作流程产生负面影响。因此&#xff0c;渲染平台若能提供实时预览渲染进度和效果的功能&#xf…