一、网络流问题的数学定义1.1 流网络（Flow Network）流网络 $G = (V, E)$ 是一个有向图，满足： 容量（Capacity）：每条边 $(u, v) \in E$ 有非负容量 $c(u, v) \geq 0$。若 $(u, v) \notin E$ 则 $c(u, ...

一、问题定义与应用背景1.1 All-Pairs Shortest Paths (APSP)给定带权有向图 $G = (V, E)$，其中 $|V| = n$，边权函数 $w: E \to \mathbb{R}$。 目标：对每对顶点 $(u, v)$（$u, v \in V$）， ...

问题定义单源最短路径（Single-Source Shortest Path, SSSP）问题：给定带权有向图 $G = (V, E)$ 和源点 $s \in V$，找出从 $s$ 到所有其他顶点 $v \in V$ 的最短路径。 最短路径的权值定义为路径上所有边的权值之和：$$\delt ...

一、问题定义与基本概念1.1 生成树的数学定义给定连通无向带权图 $G = (V, E)$，其中每条边 $(u, v)$ 有权重 $w(u, v) \in \mathbb{R}$。生成树（Spanning Tree） 是 $G$ 的一个子图 $T = (V, E_T)$，满足 $ ...

一、图的基本概念与数学定义1.1 图的数学定义图（Graph）是一个二元组 $G = (V, E)$，其中 $V$ 是顶点（Vertex）的有限集合，$E \subseteq V \times V$ 是边（Edge）的集合。设 $|V| = n$，$|E| = m$。 ...

一、问题定义不相交集数据结构（Disjoint Set Union，DSU），通常称为并查集（Union-Find），维护一组互不相交的动态集合 $S = {S_1, S_2, \ldots, S_k}$。每个集合有一个代表元（representative），通常是集合中的某个特定成员。 ...

一、引言：超越比较排序模型的优先队列1.1 比较模型的下界所有基于元素间比较的优先队列（二叉堆、二项堆、斐波那契堆等）的 insert、extractMin、decreaseKey 等操作，都存在 $\Omega(\log n)$ 的信息论下界。 但如果我们能够放弃”比较”的范式呢？如果键值来自一个 ...

一、引言：为什么我们需要斐波那契堆1.1 二叉堆的局限标准二叉堆（Binary Heap）支持以下操作的复杂度： insert：$O(\log n)$ findMin：$O(1)$ extractMin：$O(\log n)$ decreaseKey：$O(\log n)$ 对于 Dijkstr ...

一、为什么需要摊还分析1.1 最坏情况分析的问题传统的时间复杂度分析聚焦于单次操作的最坏情况。例如： 动态数组插入：最坏 $O(n)$（触发扩容时） 二叉堆插入：最坏 $O(\log n)$ 但这可能过分悲观。以动态数组为例，$n$ 次连续插入的最坏总时间并非 $n \times O(n) &# ...

一、贪心算法的核心思想与理论框架贪心算法（Greedy Algorithm）在每一步选择中都采取当前状态下看起来最优的选择，期望通过一系列局部最优决策最终达到全局最优解。贪心算法的精妙之处在于——对于满足特定性质的问题，这种”短视”的策略恰好能得到全局最优解；但对于另一些问题，贪心策略可能导致任意差 ...