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

9.12总结

今天学了树状dp和tarjan

树状dp

树状dp,是一种在树形数据结构上应用的动态规划算法。动态规划(DP)通常用于解决最优化问题,通过将问题分解为相对简单的子问题来求解。在树形结构中,由于树具有递归和子结构的特性,因此非常适合应用动态规划来求解。

特点与步骤:

定义状态:首先,需要为树中的每个节点定义一个或多个状态,这些状态通常表示以该节点为根的子树满足某种条件的最优解。

状态转移方程:然后,根据问题的性质,建立状态转移方程。状态转移方程描述了如何由子节点的状态推导出父节点的状态。

遍历树:通常使用深度优先搜索(DFS)来遍历整棵树,并在遍历过程中计算每个节点的状态。遍历的顺序一般是先遍历子节点,再计算父节点的状态,这样可以保证在计算父节点状态时,其子节点的状态已经被计算出来。

Tarjan算法

Tarjan算法是一种用于求解有向图强连通分量的高效算法。强连通分量是指有向图中的一个极大强连通子图,即该子图中的任意两个顶点都互相可达。

核心思想:

Tarjan算法基于深度优先搜索(DFS),利用DFS过程中产生的递归栈和节点的时间戳等信息来判断强连通分量。

关键步骤:

DFS遍历:首先,对有向图进行深度优先搜索。

时间戳记录:为每个节点记录两个时间戳,dfn[u]表示节点u被访问的时间(即DFS序),low[u]表示节点u通过DFS树中的边能回溯到的最早的栈中节点的dfn值。

强连通分量判定:在DFS过程中,如果某个节点u的dfn[u]等于low[u],则说明以u为根的子树中的所有节点构成了一个强连通分量。

 

http://www.lryc.cn/news/436683.html

相关文章:

  • 小众创新组合!LightGBM+BO-Transformer-LSTM多变量回归交通流量预测(Matlab)
  • 《CSS新世界》书评
  • python 实现euler modified变形欧拉法算法
  • strcpy 函数及其缺点
  • 区块链-P2P(八)
  • 数据库管理的利器Navicat —— 全面测评与热门产品推荐
  • 如何让Google收录我的网站?
  • 03 Flask-添加配置信息
  • Codes 开源研发项目管理平台——敏捷测试管理创新解决方案
  • 耗时一个月,我做了一个网页视频编辑器
  • uniapp 做一个查看图片的组件,图片可缩放移动
  • 卡车配置一键启动无钥匙进入手机控车
  • 计算机网络基础概念 交换机、路由器、网关、TBOX
  • labview禁用8080端口
  • 字符串的KMP算法详解及C/C++代码实现
  • 2024年数学建模比赛题目及解题代码
  • BERT 论文逐段精读【论文精读】
  • 在Flask中实现跨域请求(CORS)
  • 在桌面商业分析应用程序中启用高级 Web UI
  • CentOS Stream 8 通过 Packstack 安装开源 OpenStack(V版)
  • OpenSSL工具验证RSA证书
  • 架构师白话分布式系统
  • C++ 中 vector 的常用功能介绍
  • [QT] QT事件与事件重写
  • c# 视觉识别图片文字 二维码
  • UEFI——访问PCI/PCIE设备(二)
  • 决策树算法的介绍与应用
  • 杰发科技Bootloader(3)—— 基于7801的APP切到Boot
  • Leetcode面试经典150题-138.随机链表的复制
  • freemarker模板学习笔记