【图论】图的存储--链式前向星存图法以及深度优先遍历图

2024-04-10 19:28

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

图的存储

介绍

无向图-就是一种特殊的有向图->

只用考虑有向图的存储即可

有向图

  • 邻接矩阵
  • 邻接表

邻接表

在这里插入图片描述

存储结构:
(为每一个点开了一个单链表,存储这个点可以到达哪个点)

  • 1:3->4->null
  • 2:1->4->null
  • 3:4->null
  • 4:null
插入一条新的边

在这里插入图片描述

比如要插一条边:2->3

  • 先找到 2 对应的单链表
  • 然后将 3 插入到单链表里面去(一般使用头插)

对应的结构变化为:

  • 1:3->4->null
  • 2:3->1->4->null
  • 3:4->null
  • 4:null
插入边 Coding Part
#include <iostream>
#include <cstring>
#define p(e) print(e, sizeof(e)/sizeof(int))
using namespace std;const int N = 100010, M = N * 2;
//N表示结点数量上限,M表示结点数值上限int h[N], e[M], ne[M], idx;//插入一个a->b
inline void add(int a, int b) {e[idx] = b, ne[idx] = h[a], h[a] = idx++;/** idx是没有使用的空结点索引* 先给这个位置赋值b					# e[idx] = b* 然后让这个结点指向头结点			# ne[idx] = h[a]* 然后再更新头结点 					# h[a] = idx++* 同时让idx移动到新的空结点索引中去 # idx++*/
}inline void print(int arr[], int n) {for (int i = 0; i < n; i++) cout << arr[i] << ' ';cout << endl;
}int main() {memset(h, -1, sizeof h);
}

遍历图

深度优先方法遍历图
  • 需要使用一个bool数组存放是否遍历的状态
  • 然后进行深度优先遍历
#include <iostream>
#include <cstring>using namespace std;const int N = 100010, M = N * 2;
//N表示结点数量上限,M表示结点数值上限int h[N], e[M], ne[M], idx;
bool st[N];
//插入一个a->b
inline void add(int a, int b) {e[idx] = b, ne[idx] = h[a], h[a] = idx++;/** idx是没有使用的空结点索引* 先给这个位置赋值b					# e[idx] = b* 然后让这个结点指向头结点			# ne[idx] = h[a]* 然后再更新头结点 					# h[a] = idx++* 同时让idx移动到新的空结点索引中去 # idx++*/
}inline void dfs(int u) {st[u] = true;cout << u << ' ' ;for (int i = h[u]; i != -1; i=ne[i]) {int j = e[i];if (!st[j]) dfs(j);}
}int main() {memset(h, -1, sizeof h);memset(st, false, sizeof st);add(1, 3);add(3, 5);add(3, 6);add(1, 2);add(1, 8);dfs(1);
}
题目:树的重心

给定一棵树,树中包含n个结点,(编号为1~n)和n-1个无向边
请找到树的重心,并输出将重心删除后,剩余各个连通块中点数的最大值。
重心定义:重心是指树中的一个结点,如果将这个结点删除后,剩余各个连通块中点数的最大值最小,那么这个结点被称为树的重心。
输入格式
第一行包含整数 n,表示树的结点数。
接下来 n-1 行,每行包含两个整数 ab,表示 ab 之前存在的一条边。

输出格式
输出一个整数 m,表示重心的所有子树中最大子树的结点数目。

数据范围
1 <= n <= 105

输入样例

9
1 2
1 7
1 4
2 8
2 5
4 3
3 9
4 6

输出样例

4

答案代码

#include <iostream>
#include <cstring>using namespace std;const int N = 100001, M = N*2;
int h[N], e[M], ne[M], idx;
bool st[N];//a->b
void add(int a, int b) {e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}/*遍历模板*/
void dfs_template(int u) {st[u] = true;cout << u << ' ';for (int i = h[u]; i != -1; i = ne[i]) {int j = e[i];if (!st[j]) {dfs_template(j);}}
}int n;										//n为题目输入的结点数量
int ans = INT_MAX;							//初始化题目要求的最小值
int dfs(int u) {//每一棵树找到最大连通块的数量st[u] = true;int sum = 1, res = 0;							//sum统计子结点(包括自己)的数量, res统计儿子树最大连通块数量for (int i = h[u]; i != -1; i = ne[i]) {int j = e[i];if (!st[j]) {int s = dfs(j);sum += s;							//加上子节点的数量res = max(s, res);					//找到子树中的最大连通块}}res = max(res, n-sum);							//和父亲树进行比较ans = min(ans, res);							//更新答案return sum;
}int main() {memset(h, -1, sizeof ne);cin >> n;for (int i = 0; i < n-1; i++) {int a, b;cin >> a >> b;add(a, b), add(b, a);}dfs(1);cout << ans << endl;
}
宽度优先方法遍历图

补充两个图论的概念:

  • 重边: 例如,存在两条 1->2 的边,叫重边
  • 自环:例如,1->1叫自环
题目:图中点的层次

这篇关于【图论】图的存储--链式前向星存图法以及深度优先遍历图的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

SpringCloud动态配置注解@RefreshScope与@Component的深度解析

《SpringCloud动态配置注解@RefreshScope与@Component的深度解析》在现代微服务架构中,动态配置管理是一个关键需求,本文将为大家介绍SpringCloud中相关的注解@Re... 目录引言1. @RefreshScope 的作用与原理1.1 什么是 @RefreshScope1.

C# WinForms存储过程操作数据库的实例讲解

《C#WinForms存储过程操作数据库的实例讲解》:本文主要介绍C#WinForms存储过程操作数据库的实例,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、存储过程基础二、C# 调用流程1. 数据库连接配置2. 执行存储过程(增删改)3. 查询数据三、事务处

Python 中的异步与同步深度解析(实践记录)

《Python中的异步与同步深度解析(实践记录)》在Python编程世界里,异步和同步的概念是理解程序执行流程和性能优化的关键,这篇文章将带你深入了解它们的差异,以及阻塞和非阻塞的特性,同时通过实际... 目录python中的异步与同步:深度解析与实践异步与同步的定义异步同步阻塞与非阻塞的概念阻塞非阻塞同步

Redis中高并发读写性能的深度解析与优化

《Redis中高并发读写性能的深度解析与优化》Redis作为一款高性能的内存数据库,广泛应用于缓存、消息队列、实时统计等场景,本文将深入探讨Redis的读写并发能力,感兴趣的小伙伴可以了解下... 目录引言一、Redis 并发能力概述1.1 Redis 的读写性能1.2 影响 Redis 并发能力的因素二、

Oracle存储过程里操作BLOB的字节数据的办法

《Oracle存储过程里操作BLOB的字节数据的办法》该篇文章介绍了如何在Oracle存储过程中操作BLOB的字节数据,作者研究了如何获取BLOB的字节长度、如何使用DBMS_LOB包进行BLOB操作... 目录一、缘由二、办法2.1 基本操作2.2 DBMS_LOB包2.3 字节级操作与RAW数据类型2.

最新Spring Security实战教程之表单登录定制到处理逻辑的深度改造(最新推荐)

《最新SpringSecurity实战教程之表单登录定制到处理逻辑的深度改造(最新推荐)》本章节介绍了如何通过SpringSecurity实现从配置自定义登录页面、表单登录处理逻辑的配置,并简单模拟... 目录前言改造准备开始登录页改造自定义用户名密码登陆成功失败跳转问题自定义登出前后端分离适配方案结语前言

Java实现数据库图片上传与存储功能

《Java实现数据库图片上传与存储功能》在现代的Web开发中,上传图片并将其存储在数据库中是常见的需求之一,本文将介绍如何通过Java实现图片上传,存储到数据库的完整过程,希望对大家有所帮助... 目录1. 项目结构2. 数据库表设计3. 实现图片上传功能3.1 文件上传控制器3.2 图片上传服务4. 实现

C语言中的浮点数存储详解

《C语言中的浮点数存储详解》:本文主要介绍C语言中的浮点数存储详解,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1、首先明确一个概念2、接下来,讲解C语言中浮点型数存储的规则2.1、可以将上述公式分为两部分来看2.2、问:十进制小数0.5该如何存储?2.3 浮点

MySQL常见的存储引擎和区别说明

《MySQL常见的存储引擎和区别说明》MySQL支持多种存储引擎,如InnoDB、MyISAM、MEMORY、Archive、CSV和Blackhole,每种引擎有其特点和适用场景,选择存储引擎时需根... 目录mysql常见的存储引擎和区别说明1. InnoDB2. MyISAM3. MEMORY4. A

Redis 内存淘汰策略深度解析(最新推荐)

《Redis内存淘汰策略深度解析(最新推荐)》本文详细探讨了Redis的内存淘汰策略、实现原理、适用场景及最佳实践,介绍了八种内存淘汰策略,包括noeviction、LRU、LFU、TTL、Rand... 目录一、 内存淘汰策略概述二、内存淘汰策略详解2.1 ​noeviction(不淘汰)​2.2 ​LR