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

2024-04-11 05:36

本文主要是介绍【图论】详解链式前向星存图法+遍历法,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

细说链式前向星存图法

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

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

在这里插入图片描述

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

准备三个数组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);
}

这篇关于【图论】详解链式前向星存图法+遍历法的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/893199

相关文章

Python基础文件操作方法超详细讲解(详解版)

《Python基础文件操作方法超详细讲解(详解版)》文件就是操作系统为用户或应用程序提供的一个读写硬盘的虚拟单位,文件的核心操作就是读和写,:本文主要介绍Python基础文件操作方法超详细讲解的相... 目录一、文件操作1. 文件打开与关闭1.1 打开文件1.2 关闭文件2. 访问模式及说明二、文件读写1.

详解C++中类的大小决定因数

《详解C++中类的大小决定因数》类的大小受多个因素影响,主要包括成员变量、对齐方式、继承关系、虚函数表等,下面就来介绍一下,具有一定的参考价值,感兴趣的可以了解一下... 目录1. 非静态数据成员示例:2. 数据对齐(Padding)示例:3. 虚函数(vtable 指针)示例:4. 继承普通继承虚继承5.

前端高级CSS用法示例详解

《前端高级CSS用法示例详解》在前端开发中,CSS(层叠样式表)不仅是用来控制网页的外观和布局,更是实现复杂交互和动态效果的关键技术之一,随着前端技术的不断发展,CSS的用法也日益丰富和高级,本文将深... 前端高级css用法在前端开发中,CSS(层叠样式表)不仅是用来控制网页的外观和布局,更是实现复杂交

Linux换行符的使用方法详解

《Linux换行符的使用方法详解》本文介绍了Linux中常用的换行符LF及其在文件中的表示,展示了如何使用sed命令替换换行符,并列举了与换行符处理相关的Linux命令,通过代码讲解的非常详细,需要的... 目录简介检测文件中的换行符使用 cat -A 查看换行符使用 od -c 检查字符换行符格式转换将

详解C#如何提取PDF文档中的图片

《详解C#如何提取PDF文档中的图片》提取图片可以将这些图像资源进行单独保存,方便后续在不同的项目中使用,下面我们就来看看如何使用C#通过代码从PDF文档中提取图片吧... 当 PDF 文件中包含有价值的图片,如艺术画作、设计素材、报告图表等,提取图片可以将这些图像资源进行单独保存,方便后续在不同的项目中使

Android中Dialog的使用详解

《Android中Dialog的使用详解》Dialog(对话框)是Android中常用的UI组件,用于临时显示重要信息或获取用户输入,本文给大家介绍Android中Dialog的使用,感兴趣的朋友一起... 目录android中Dialog的使用详解1. 基本Dialog类型1.1 AlertDialog(

C#数据结构之字符串(string)详解

《C#数据结构之字符串(string)详解》:本文主要介绍C#数据结构之字符串(string),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录转义字符序列字符串的创建字符串的声明null字符串与空字符串重复单字符字符串的构造字符串的属性和常用方法属性常用方法总结摘

Java中StopWatch的使用示例详解

《Java中StopWatch的使用示例详解》stopWatch是org.springframework.util包下的一个工具类,使用它可直观的输出代码执行耗时,以及执行时间百分比,这篇文章主要介绍... 目录stopWatch 是org.springframework.util 包下的一个工具类,使用它

Java进行文件格式校验的方案详解

《Java进行文件格式校验的方案详解》这篇文章主要为大家详细介绍了Java中进行文件格式校验的相关方案,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录一、背景异常现象原因排查用户的无心之过二、解决方案Magandroidic Number判断主流检测库对比Tika的使用区分zip

Java实现时间与字符串互相转换详解

《Java实现时间与字符串互相转换详解》这篇文章主要为大家详细介绍了Java中实现时间与字符串互相转换的相关方法,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录一、日期格式化为字符串(一)使用预定义格式(二)自定义格式二、字符串解析为日期(一)解析ISO格式字符串(二)解析自定义