树上问题
8 items
拓扑排序
本文将介绍拓扑排序，用 Kahn 算法按入度为零逐步取点排序，同时判定有向图是否有环。
最短路
本文将介绍最短路的 Floyd、Bellman–Ford、Dijkstra 与 Johnson。
生成树
本文将介绍最小生成树的 Kruskal、Prim、Boruvka 及最小树形图、瓶颈生成树。
连通性
本文将讲解基于 Tarjan 的连通性，涵盖强连通与双连通分量、割点与桥、圆方树及 2-SAT。
环计数
本文将介绍三元环计数，通过按度数给边定向、枚举出边邻居完成统计，复杂度 O(m√m)。
最小环
本文将介绍最小环的求法，稠密图用 Floyd 枚举中间点，稀疏图枚举删边后跑 Dijkstra。
欧拉图
本文将介绍欧拉路径与欧拉回路的存在性判定，并用 Hierholzer 算法构造字典序最小的方案。
二分图
本文将介绍二分图的定义与判定，说明它等价于不含奇环，可用黑白染色法在线性时间内判断。
网络流
本文将介绍网络流，涵盖最大流的增广路思想、Edmonds–Karp、最小费用最大流与上下界网络流。
图匹配
本文将介绍三类图匹配，二分图最大匹配的匈牙利算法、最大权匹配的 KM 算法与一般图的带花树算法。
Prüfer 序列
本文将介绍 Prüfer 序列，它建立带标号无根树的双射，并推出凯莱公式与度数受限树计数。
矩阵树定理
本文将介绍矩阵树定理，用基尔霍夫矩阵的主子式行列式对图的生成树计数，并推广到带权图与有向图。