最小生成树

问题描述

生成树

设 $G = (V, E)$ 是一个边加权无向连通图。$G$ 的生成树是无向树 $S = (V, T)$，$T \subseteq E$。$W$ 是 $G$ 的权函数，$T$ 权值定义为 $W(T) = \sum_{(u, v) \in T}{W(u, v)}$。

最小生成树

$G$ 的最小生成树是使 $W(T)$ 最小的 $G$ 的生成树。

• 输入：无向连通图 $G = (V, E)$，权函数 $W$。
• 输出：$G$ 的最小生成树。

Kruskal 算法

• 初始时所有顶点自成一集合。
• 在图上选权值最小的边 $e_{min}$，判断 $e_{min}$ 两端点是否属于不同集合 $c_i$ 和 $c_j$。
  • 若是，将 $c_i$ 和 $c_j$ 用 $e_{min}$ 连接成同一个集合。
  • 否则，舍弃 $e_{min}$。
• 重复上一过程，直到所有顶点在同一集合。

并查集

并查集是一种数据结构，类似于《离散数学》中等价类的划分。这种数据结构非常适合处理如下两大问题：

• 需要经常合并集合
• 需要经常查找元素属于哪个集合

采用并查集的数据结构，可以提高 Kruskal 算法中判断边的两端点是否属于不同集合的效率。

并查集支持以下操作：

• 初始化 UFSets(s)：将 s 中的每个元素自成一个集合。
• 合并 Union(root1, root2)：合并集合 root1 和 root2。
• 查找 Find(x)：查找元素 x 属于哪个集合。

并查集的表示

通常用双亲表示法表示的树作为并查集的基础数据结构（在内存中是连续的存储空间）。数组下标对应每个元素，数组的值表示指向父结点的指针。负数表示没有父结点，其绝对值表示集合中一共有多少个元素。

记录集合中总的元素个数的意义在于，将结点数更少的集合作为结点数更多的集合的根的子树能够提高并查集的查询效率。

路径压缩

并查集的代码实现

TODO

算法代码

TODO

Prim 算法

Prim 算法非常类似于点灯游戏。它首先“点亮”一个源，然后结合广度优先搜索算法，每次找边权重最小的相邻结点“点亮”，直到所有的结点均“点亮”。

算法代码

TODO