CrabPeelMyShell

最小生成树MST及其构建算法、最短路径算法

生成树 Spanning Tree 给定连通图中的 $|V|=n$ 个节点,使用 n-1 条边将这些点连接起来。在这些点中选取一个根节点,即成为一颗生成树。生成树不是唯一的,可以选取不同的顶点作为根节点。 生成树可以很奇特: 最小生成树 Minimal Spanning Tree 如果我们将这个图的边添加权重,那么所包含的边权重最小的生成树就是最小生成树。对于没有显式给出权重...

并查集 Disjoint Set

在离散数学(Discrete Mathematics)中我们曾经学习过,“一个等价关系可以将一个集合中的元素划分为多个等价类”,这多个等价类就是多个不相交的集合,我们称其为并查集(Disjoint Set)。 从翻译的角度上来看,并查集和 Disjoint 好像并没有什么关系。中文上的“并查”指的是在这个数据结构上可以进行的操作:并(Union) 和查(Find)。但在英语上,只是说明了他...