Category: 图论

2023
算法图论

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

算法图论

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

问题背景并查集回炉 基础并查集功能和题目列表: 并查集 带权并查集功能和题目列表: 带权并查集 并查集维护平面点的横纵坐标 并查集时光倒流 对于用[带权]并查集解决加边连通性的问题，我们之前处理过以下几类问题: 加边过程中动态地处理【两个点 x, y 是否连通】的查询问题 加边过程中动态地处理【某个点 x 对应的连通分量的大小】的查询问题 加边过程中动态地处理【当前连通分量的个数】的查询问题

2020
算法图论

DAG判定

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

算法图论

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

并查集 带权并查集 并查集维护坐标点的办法 维护点编号 维护横纵坐标 求连通分量个数的一种方法：枚举点，将代表元插入哈希表，由哈希表执行去重 947. 移除最多的同行或同列石头 1267. 统计参与通信的服务器 $0 场景二维平面有 N 个点，每个点有一个坐标 (x, y)，每两个点，如果横坐标相同或纵坐标相同，则视为在同一个连通分量中。问给定的 N 个点构成多少个连通分量。 (1) 并

算法图论

并查集时光倒流

并查集 带权并查集 并查集时光倒流 803. 打砖块 $0 并查集时光倒流对于维护加边连通性的过程，并查集是非常有力的。 但是由于并查集合并后一般是不支持回滚的，仅仅可以通过开栈的方式实现撤销合并，即回滚一步。 因此如果要维护一个删边连通性的过程，并查集就无法完成了。但是有些问题可以逆向思维，即正向思维是 初态图 -> 删边 -> 终态图，逆向思维就变成了 终态图 -> 加边

算法图论

下标索引堆优化Prim

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

算法图论

DAG典型应用-活动网络

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

算法图论

有向图的必经点,支配树

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

算法图论

LCA,树上倍增,树上差分

LCA 向上标记法(搜索) 236. 二叉树的最近公共祖先 / 面试题 04.08. 首个共同祖先 树上倍增 1483. 树节点的第 K 个祖先 tarjan 算法 LCA 题目 1257. 最小公共区域 235. 二叉搜索树的最近公共祖先 1123. 最深叶节点的最近公共祖先 LCA 应用 树上差分 次小生成树 支配树 $1 LCA问题 给定一棵有根树，若 z 既是 x

算法图论

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。此外本题还有一个值

算法图论

DFS序,欧拉序,dfn序

DFS序,欧拉序,dfn序的定义和性质 经典问题 $1 DFS序,欧拉序,dfn序的定义和性质(1) DFS 序定义DFS 过程中对于某节点进入这个节点的子树和离开子树的顺序 性质 满足每个节点都会在dfs序上出现恰好两次 任意子树的 dfs 序都是连续的 记节点 x 在 dfs 序中的两次出现的位置为 L[x], R[x]，则区间 [L[x], R[x]] 就是以 x 为根的子树的 d

算法图论

二分图判定

摘要: 本文介绍欧拉路径的判定定理、算法、代码模板和例题。 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的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 负环在图论中，如果一条边的权值是负数，则为负权，如果图中存在一个环，还上各个边的权值之和为负数，则为负环。 在 带权图最短路径 中，各种单

算法图论

DFS拓扑排序

BFS 拓扑排序 DFS 的后序遍历实现拓扑排序 代码与 DFS 判定有向图的环几乎一样: 有向图的环 类似的算法：有向图的连通分量 对有向图进行 DFS，访问节点顺序的逆序就是一个拓扑排序结果。因此可以在 DFS 的回溯阶段将当前节点加入到遍历到的节点的列表中，相当于 DFS 后序遍历。 但这里有一个问题有如果有向图有环，照样可以 DFS 产生一个访问节点顺序的逆序。解法是在进行 DFS

算法图论

基环树

基环树概念 基环树常见处理方式 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 本文我们来学习一个图论中常见的问题：欧拉路径。首先介绍欧拉路径的一些判定定理，包括有向图欧拉

算法图论

无向图的割点

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

算法图论

DFS树和BFS树

背景：大部分的算法，可以用 DFS/BFS 之一的，用另一个也能完成。但是寻找桥的算法，只能用 DFS 做，主要的原因就是需要用到 DFS 独特的性质。 DFS 和 BFS 各自有自己的特性，BFS 的特性主要就是 BFS 的过程直接实现了无权图最短路径的特性。这里主要关注 DFS 的特性。 $1 BFS 遍历树和 DFS 遍历树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

算法图论

哈密顿路径

哈密顿路的定义和性质 图论4-欧拉图,哈密顿图 状态压缩DP 寻找哈密顿路: DFS，指数级 模板题: 91. 最短Hamilton路径 847. 访问所有节点的最短路径 943. 最短超级串 980. 不同路径 III 模板题: 91. 最短Hamilton路径给定一张 n 个点的带权无向图，点从 0∼n−1 标号，求起点 0 到终点 n−1 的最短 Hamilton 路径

算法图论

拓扑排序的方案数

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

算法图论

带权并查集

并查集 带权并查集 集合级的权: 一般是连通分量中的属性，例如元素个数，最值等，查找过程无影响 边级的权：节点到父节点的某种指标，例如长度，查找和合并都会对边权有影响 模板: 399. 除法求值 题目 集合级的权 128. 最长连续序列 连通分量的大小 面试题 17.07. 婴儿名字 连通分量的属性 952. 按公因数计算最大组件大小 连通分量的大小 1061. 按字典序排列最小的等效字符串

算法图论

并查集

基本操作：same(x, y), union(x, y), find(x) 路径压缩，按秩合并 解决的问题： 加边连通性：不断加边，同时问某两个点是否连通 Kruskal 最小生成树 连通分量：判定，个数，大小, 属性 环：判定，长度，个数 模板 547. 朋友圈 并查集的回滚 题目 (1) 加边连通性 261. 以图判树 305. 岛屿数量 II 1627. 带阈值的图连通性 1101.

算法图论

BFS拓扑排序

拓扑排序算法及其 BFS 实现(Kahn算法) 求排序结果 判断图中是否有环 拓扑排序的 DFS 实现(开栈保存拓扑排序的结果) 拓扑排序的存在性 拓扑排序的唯一性 拓扑排序的方案数 题目 802. 找到最终的安全状态 207. 课程表 269. 火星词典 210. 课程表 II 444. 序列重建 1203. 项目管理 329. 矩阵中的最长递增路径 $1 拓扑排序算法拓扑排序：

算法图论

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

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

算法图论

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

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