Category: 图论

2023
算法图论

含集合级信息的并查集

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

算法图论

树上差分

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

算法图论

Floyd算法

摘要: Floyd算法的原理与代码模板 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 历届图灵奖得主基本上都有高学历、高学位，绝大多数有博士头衔。这是可以理解的，因为创新型人才需要有很好的文化素养

算法图论

迪杰斯特拉算法(Dijkstra)

摘要: 迪杰斯特拉算法原理与代码模板 【对数据分析、人工智能、金融科技、风控服务感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：潮汐朝夕我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 迪杰斯特拉（Edsger Wybe Dijkstra）在一个充满科学气息的家庭背景中长大，父亲

2022
算法图论

二分图匹配-最大匹配

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

2021
算法图论

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

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

算法图论

图论题目汇总

本文总结了力扣上 2000 题以内的关于图论的 40 道题。将场景相同的放到了一起。 图论是数学的一个分支，以图为研究对象。图是由若干给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系。 在计算机中，图论算法提供的是一种对很多问题都有效的一种简单而系统的建模方式。很多问题都可以转化为图论问题，然后用图论的基

算法图论

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

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

2020
算法图论

DAG判定

$0 场景给定有向图 D，判定 D 是否为 DAG 分析等价于判定有向图 D 中有没有环，因此判定 DAG 的算法与有向图判定环的算法相同。以下为复习。 有向图判定环的方法：有向图的环 BFS (拓扑排序) 如果拓扑排序后的排序列表长度小于 n，则无法拓扑排序，即 D 不是 DAG。 代码模板1234567891011121314151617181920212223242526class

算法图论

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

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

算法图论

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

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

算法图论

下标索引堆优化Prim

1135. 最低成本联通所有城市 邻接表 + 二叉堆 Prim 最小生成树 $O(E\log E)$ 邻接表 + 下标索引堆 Prim 下标索引堆 在下标索引堆模板的基础上的修改 $O(E\log V)$ 完整代码 $0 1135. 最低成本联通所有城市$1 邻接表 Prim 参考: 最小生成树 123456将 0 加入集合 Twhile 尚有点没有进入集合 T 从剩下的点中

算法图论

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

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

算法图论

DAG典型应用-活动网络

活动网络 AOV 网络 拓扑排序 AOE 网络 关键路径算法 建图，超级源，超级汇 超级源到超级汇的单源单汇最长路径 BFS 拓扑序 DP 预处理各节点信息求关键活动 【模板: AOE 网络求关键活动】 PTA 7-11 关键活动 $0 活动网络活动网络(activity network)是一种 DAG，可以用来描述生产计划、施工过程、生产流程、程序流程等工程中各子工程的安

算法图论

有向图的必经点,支配树

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

算法图论

最近公共祖先问题

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

算法图论

k短路

K 短路 178. 第K短路 问题给定一张N个点（编号1,2…N），M条边的有向图，求从起点S到终点T的第K短路的长度，路径允许重复经过点或边。 注意： 每条最短路中至少要包含一条边。 数据格式 第一行包含两个整数N和M。接下来M行，每行包含三个整数A,B和L，表示点A与点B之间存在有向边，且边长为L。最后一行包含三个整数S,T和K，分别表示起点S，终点T和第K短路。 12341 <&

算法图论

基于 Floyd 搜索有向图的所有最小环

搜索有向图最小环长度并返回一个最小环 无向图的环 有向图的环 Floyd 搜索有向图所有的最小环 应用：854. 相似度为 K 的字符串 注: 最小环的问题也可以用 dijkstra 求解 $1 求有向图最小环长度并返回一个最小环有向图的环的基本概念参考：有向图的环 无向图 Floyd 求最小环的过程参考 无向图的环，有向图的情况类似。 考虑 Floyd 的过程： 在最外层 k 在迭代过

算法图论

建图的CornerCase

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

算法图论

遍历序的概念与性质

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

算法图论

二分图判定

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

算法图论

差分约束

差分约束模型问题差分约束系统是一种特殊的 N 元一次不等式组，有 N 个变量 $X_{1} ~ X_{N}$ 以及 M 个约束条件。 每个约束条件室友两个变量做差得到的： X_{i} - X_{j} \leq c_{k} \\ c_{k} 为常数，1 \leq i,j \leq N, 1 \leq k \leq M问题：求出一组解 $X_{i} = a_{i}, i=1,2,…,N$，使得 M

算法图论

负环

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

算法图论

基环树

基环树概念 基环树常见处理方式 N 个点的树有 N - 1 条边，在树上任意加一条边，会形成一个环，除了环之外，其余部分由若干子树构成。 这种 N 个点 N 条边的连通无向图称为基环树。若干基环树组成的森林，为基环树森林。 有向图也有类似概念，N 个点，N 条边: 每个节点有且仅有一条入边的有向图，称为外向树。 每个节点有且仅有一条出边的有向图，称为内向树。 基环树结构在图论中也算比较

算法图论

超级源

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

算法图论

最小生成树

1135. 最低成本联通所有城市 Kruskal 算法 切分定理以及 Kruskal 算法贪心的正确性 Kruskal 可以顺便判环 Prim 算法 邻接矩阵 $O(V^{2})$ 邻接表+堆 $O(E\log E)$ 超级源 $1 Kruskal 算法算法12345cost = 0循环 n - 1 次 (选 n - 1 条边): 按照 w 从小到大枚举边 edge &#

算法图论

有向图的环

有向图判定环 207. 课程表 DFS BFS(拓扑排序) 维护环的长度 最小环 经过特定点的最小环 有向图判定环207. 课程表 dfs在无向图判定环时，找到一个点，它不是 prev 点而又在此前遍历过，则形成环 有向图：以前遍历过并不代表形成环，办法是标记当前搜索路径，当回溯后，相应点要从标记中去掉。 123visited[i] = 0 未考查过visited[i] &

算法图论

无向图的环

无向图判定环 DFS 染色 BFS 染色 并查集 拓扑排序 返回一条在环上的边/判定具体的边是否在环上 684. 冗余连接 维护环的长度 d[u] := u 到源点 start 的距离 / d[i][j] := i 到 j 的距离 1559. 二维网格图中探测环 无向带权图最小环问题：344. 观光之旅 其它 环的计数 返回所有简单环 对环做缩点 $1 无向图判定环(模板)

算法图论

无向图的双连通分量

无向双连通图的定义 点双连通图 边双连通图 双连通分量 DCC 点双连通分量 v-DCC 边双连通分量 e-DCC 双向连通图的判定定理(充要条件) 双向连通图算法(Tarjan) e-DCC 求法 e-DCC 缩点 v-DCC 求法 v-DCC 缩点 $1 无向双连通图的定义对于无向连通图: 若不存在割点，则称其为点双连通图 若不存在桥，则称其为边双连通图 $2 双连通分量

算法图论

tarjan算法

一种由Robert Tarjan提出的求解有向图强连通分量的线性时间的算法。 Tarjan 算法基于无向图的 DFS，可以在 $O(N + E)$ 求出无向图的割点和桥，进一步可以求出无向图的双连通分量。 Tarjan 算法涉及时间戳，搜索树，以及追溯值的概念。 节点 node 的时间戳是指在 DFS 中，按照每个节点第一次被访问的顺序给 N 个节点做标记，记为 ord[node] 或者 dfn

算法图论

无向图的连通分量

连通分量的图论阐释：图论1-基本概念 无向图的连通分量算法 DFS BFS 并查集(可以处理动态加边以及多次查询) 最大连通分量 695. 岛屿的最大面积 BFS 处理无向图连通分量 连通分量个数 200. 岛屿数量 并查集处理无向图连通分量 枚举连通分量 1202. 交换字符串中的元素 DFS 处理无向图连通分量 $1 无向图的连通分量算法DFSRef: DFS BFSRe

算法图论

欧拉路径

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

算法图论

无向图的割点

桥和割点的图论阐释：图论1-基本概念 无向图的割点 寻找割点的算法 1568. 使陆地分离的最少天数 $1 无向图的割点无限图中，如果删除某个点，与顶点相邻的边也删除，导致连通分量个数发生变化，则该点为割点。 应用：交通系统，社交网络。 无向图寻找割点的算法：DFS在 DFS 过程中，如何判断 node 是否是割点: 在桥的判定中，对于在 DFS 树上的边 (node, son)，若满足

算法图论

遍历树的概念与性质

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

算法图论

有向图的连通分量

强连通的图论定义和性质：图论1-基本概念 流图 流图的搜索树 流图的时间戳 有向图的强连通分量SCC tarjan算法 时间戳 追溯值 判定法则 Kosaraju算法 2-SAT SCC 缩点 802. 找到最终的安全状态 $1 流图有向图 D，节点集为 V，托存在 $r \in V$，满足从 r 出发能够到达 V 中所有的点，则成 D 为流图。r 称为流图的源点 与无向图的

算法图论

无向图的桥

桥和割点的图论阐释：图论1-基本概念 无向图的桥 寻找桥的算法 1192. 查找集群内的「关键连接」 1489. 找到最小生成树里的关键边和伪关键边 $1 无向图的桥无限图中，如果删除某条边，导致连通分量个数加1，则该条边为桥。 应用：交通系统，社交网络。 一个图中可能有多个桥。 树的所有边都是桥 无向图寻找桥的算法：DFS难点在于在 DFS 中要记录哪些信息。 DFS 遍历图中的边123

算法图论

哈密顿路径

摘要: 本文介绍哈密顿路径的背景、算法、代码模板和例题。 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的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