Category: 图算法

2024
算法图算法

通过建图将问题转化为图上的搜索问题

摘要: 难点在于正确建图 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 各位好，今天我们来看一个通过建图将问题转化为图上的搜索问题，难点在于正确建图。 题目 2101. 引爆最多的炸弹 给你一个炸

算法图算法

无向图的最小环问题

摘要: 无线图最小环问题：Floyd变形、Dijkstra变形 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 本文我们看一下无向图中求长度最短的环的问题。 如果无向图是带权的，那么算法是在 Floy

算法图算法

带权并查集：需要多个权值以及权值为复杂结构的情况

摘要: 并查集中的集合权值很复杂的情况 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 在文章 并查集 中我们学习了并查集的原理和代码模板。我们知道并查集的结构是一个森林，其中的每一棵树表示一个集合或

算法图算法

有向无环图的反图与逆向思维

摘要: DAG 中的祖先节点 -> 反图的后代节点 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 本文我们通过一个题目来看一下有向无环图的反图的性质。首先我们简要介绍一下反图的概念以及有向无环图反图

2023
算法图算法

给定树的遍历序-重建一棵可能的树

摘要: BFS 序和 DFS 序结合的经典问题 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 在文章 遍历序的概念与性质 中，我们了解了树的各种遍历序。本文我们看一个直接的问题，如何从树的遍历序，构

算法图算法

问题规约的艺术：无向基环树的直径

摘要: 基环树的概念与例子 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 对于无向图，N 个点的树有 N - 1 条边，在树上任意加一条边，会形成一个环，除了环之外，其余部分由若干子树构成。 这种

算法图算法

含集合级信息的并查集

摘要: 带集合级信息的并查集的原理与代码模板 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 在文章 并查集 中我们学习了并查集的原理和代码模板，本文介绍带集合级信息的并查集。 我们知道并查集的结构是

算法图算法

树上差分

摘要: 树上差分算法 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 在文章 前缀和与差分，我们对一个序列定义了前缀和序列和差分序列，根据差分序列的前缀和序列是原序列，原序列区间上的增减转化为了前缀和

2022
算法图算法

二分图匹配：最大匹配，匈牙利算法

摘要: 二分图最大匹配的算法：匈牙利算法 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 对于一个无向图 G，有 N 个节点(N >= 2)，可以发分成 A, B 两个非空集合，其中 $A \c

2021
算法图算法

图论算法理论,实现与应用

摘要: 《图论算法理论，实现与应用》 【对数据分析、人工智能、金融科技、风控服务感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：潮汐朝夕我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 图论算法理论-实现及应用

算法图算法

并查集-加边过程中维护具体连通分量

摘要: 并查集在加边过程中维护具体连通分量 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 问题背景对于用含集合级信息并查集解决加边连通性的问题，我们之前处理过以下几类问题: 加边过程中动态地处理【

2020
算法图算法

DAG判定

摘要: DAG 判定算法 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 本文我们给出 DAG 的判定算法，并解决 1059. 从始点到终点的所有路径。 DAG 的判定给定有向图 $D$，判定 $D$

算法图算法

并查集维护平面点的横纵坐标

摘要: 并查集的原理与代码模板 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 此前我们详细学习过并查集的原理，比如 并查集、带边权的并查集、含集合级信息的并查集。 本文我们学习并查集的一个常见应用技

算法图算法

删边连通性：并查集+逆向思维

摘要: 并查集+逆向思维处理删边连通性问题 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 对于维护加边连通性的过程，并查集是非常有力的。 但是由于并查集合并后一般是不支持回滚的，仅仅可以通过开栈的方

算法图算法

用并查集中各集合的代表元建图，处理集合级信息

摘要: 只用并查集中各集合的代表元建图 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 本文我们来看一个并查集的高级应用，先用并查集将节点分类并维护集合级信息。然后只用集合的代表元建图，对集合级信

算法图算法

DAG典型应用-活动网络

摘要: AOV、AOE 两种活动网络。关键路径算法 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings $0 活动网络活动网络(activity network)是一种 DAG，可以用来描述生产计划、施工

算法图算法

有向图的必经点,支配树

摘要: 有向图的必经点，支配树 【对数据分析、人工智能、金融科技、风控服务感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：潮汐朝夕我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 本文我们看一个从业务场景中抽象出来的图论的问题：有向图的必经点。给定有向图上的两个点 S 和 T，从

算法图算法

最近公共祖先问题

摘要: 最近公共祖先问题的三种解法，以及一些应用 【对数据分析、人工智能、金融科技、风控服务感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：潮汐朝夕我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 在文章 树上倍增 中，我们学习了树上倍增的思想。树上倍增主要解决从某个节点向上找第

算法图算法

拓扑排序的存在性和唯一性；建图的CornerCase

摘要: 建图的各种 Corner Case 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 本文我们通过一个拓扑排序的应用问题，看一下在建图时可能遇到的各种 Corner Case。此外本题还有一个值

算法图算法

遍历序的概念与性质

摘要: 图的几种遍历序及其应用 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 对于一棵树，我们知道从根节点出发有 DFS 和 BFS 两类方法可以把树种的节点遍历一遍。如果是二叉树的话，基于 DFS

算法图算法

二部图判定定理与算法

摘要: 本文介绍二部图判定定理与二部图判定算法 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 在文章 图论1-基本概念 中我了解了二部图的定义和一些性质。 本文我们以力扣第 785 题为模板题，看一

算法图算法

负环

摘要: 负环 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 负环在图论中，如果一条边的权值是负数，则为负权，如果图中存在一个环，还上各个边的权值之和为负数，则为负环。 在 带权图最短路径 中，各种单

算法图算法

超级源

摘要: 超级源的处理技巧 【对数据分析、人工智能、金融科技、风控服务感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：潮汐朝夕我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 超级源和超级汇是图论问题中的一个处理技巧。本文我们简要介绍一下超级源和超级汇的思想，然后解决力扣 1168。

算法图算法

在有向图中判定环

摘要: 有向图的环 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 在文章 在无向图中判定环 中，我们研究了无向图判定环的问题，本文以 207. 课程表 为模板题来看一下如何判断给定的有向图是否含有环

算法图算法

在无向图中判定环

摘要: 无向图上的环的判定 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 本文我们系统梳理一下判定无向图中是否存在环的问题。首先介绍四种算法，分别为 BFS、DFS、并查集、拓扑排序，均为图上的主流

算法图算法

欧拉路径

摘要: 本文介绍欧拉路径的判定定理、算法、代码模板和例题。 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 1736 年欧拉解决七桥问题，从七桥问题出发，进一步可以抽象出欧拉路径的概念。欧拉七桥问题

算法图算法

遍历树的概念与性质

摘要: 图的遍历树的概念与性质 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 考虑图的遍历，BFS 和 DFS 过程中，每个节点都有一个深度或者层次，也就是到作为起点的节点的距离。各个节点按照深度以

算法图算法

哈密顿路径

摘要: 本文介绍哈密顿路径的背景、算法、代码模板和例题。 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 哈密顿是 19 世纪数学家、物理学家。哈密顿在数学方面主要研究代数，比如我们可能都知道线性代

算法图算法

拓扑排序的方案数

摘要: 一个综合算法问题：树形DP + BST 建树 + 预处理组合数 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 本文我们通过力扣的一个题目，来看一下拓扑排序方案数问题怎么解决。这是第 204

算法图算法

带边权的并查集

摘要: 带边权并查集的原理与代码模板 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 在文章 并查集 中我们学习了并查集的原理和代码模板，本文介绍带边权并查集。 我们知道并查集的结构是一个森林，其中的

算法图算法

并查集

摘要: 并查集的原理与代码模板 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 本文介绍并查集的原理和代码模板，最后针对并查集可以解决的几类问题，列出了一些题目列表。 $1 并查集并查集是一种可以动

算法图算法

异构图建图

摘要: 两种类型的点和边的异构图建图 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 我们知道图论的算法相对比较固定，变化的地方不多，难点在于怎样从实际问题转换为图，图中的节点、边在原问题中是什么含义

算法图算法

拓扑排序

摘要: 拓扑排序原理、代码模板、题目列表 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumFloyd算法的原理与代码模板plings 本文我们学习拓扑排序的原理、给出代码模板和题目列表，然后解决力扣 210. 拓

算法图算法

带权图最短路径的变种问题

摘要: 带权图最短路径的变种问题 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 在文章 带权图最短路径算法与实现 中我们以力扣 743 作为模板题，全面梳理了带权图最短路径的各种算法与实现。 本文

算法图算法

树上倍增

摘要: 树上倍增算法及其在最近公共祖先问题上的应用 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 在文章 树的直径 中我们学习了树的直径的算法，这是树上的一个基础问题，很多问题都可以拆解成树的直径问

算法图算法

带权图最短路径算法与实现

摘要: 带权图单源最短路 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 本文我们以力扣 743 为模板题来看一下带权图的单源最短路问题的各种算法的原理以及实现。涉及到以下算法： dkijstra