最小生成树算法

最小生成树算法(MST Algorithm) link

生成树(Spanning Tree)是无向连通图中所有顶点以及部分边所构成的一个树状无向无环连通图。生成树的权重等于生成树中所有边的权重之和，权重最小的生成树被称为最小生成树。

生成树的特点：

• 生成树的顶点数量与原图一致。$V_{mst} = V_{g}$
• 生成树的边的数量等于原图顶点数量减1。$E_{mst} = V_{g} -1$
• 生成树必须是连通的。
• 生成树必须是无环的。
• 生成树可能有多个。

最小生成树的特点：

• 当图中所有边的权重都相等时，所有的生成树都是最小生成树，权重都相等。
• 图中权重最小的边一定包含在所有最小生成树中，最大的边一定不包含在最小生成树中。
• 若图中顶点分成两个不相交集合，集合间相连的边中权重最小的边一定包含在最小生成树中。
• 若图中形成环，如果一个边的权重严格大于其他边，则该边不会包含在任一最小生成树中。
• 若图中所有边的权重都是唯一的，则最小生成树只有一种情况。
• 生成树是最小连通图，对最小生成树移除边将成为非连通图。
• 生成树是最小无环图，往最小生成树添加边将导致环的产生。

Kruskal’s Algorithm实现 link

Kruskal’s Algorithm是一个常用的寻找无向连通图最小生成树的算法。它的核心思想是对边进行权重排序，从权重最小的边开始遍历，若边不构成闭环则添加到新图中，否则对该边进行忽略。值得注意的是，生成树边的数量满足关系式$E_{mst} = V_{g} -1$，最后一个边不需要处理（从这里可以看出权重最大的边一定不会包含在最小生成树中）。Kruskal算法的关键在于闭环检测，在选取边的时候若该边的两个端点同属于一个集合即发生了闭环，我们可以使用并查集快速判断两个元素是否处在同一集合下。

Prim’s Algorithm实现 link

Prim’s Algorithm是另外一个寻找无向连通图最小生成树的算法，它利用了生成树的不相交割集间权重最小的边一定包含在最小生成树中这条性质。核心思想是创建一个集合$S$用于跟踪已加入最小生成树的顶点，每次迭代选取$S$和$V-S$间的最小权重边加入到新图，并将其对端顶点加入到$S$，循环迭代直到所有顶点加入到$S$。$S$与$V-S$相连的边由最小权重边的对端顶点的邻接顶点中产生，一般使用小根堆来跟踪这些边并快速提取最小权重边。

Boruvka’s Algorithm实现 link

Boruvka’s Algorithm也是一个寻找无向连通图最小生成树的算法，和Prim’s Algorithm类似，它也利用了生成树的不相交割集间权重最小的边一定包含在最小生成树中这条性质。核心思想是，假设个所有顶点为仅包含一个元素的割集，对遍历所有边时更新并记录边上两连接的两个割集间的最小权重边，最后遍历这些最小权重边并对顶点所处的割集进行合并，循环迭代直到仅包含一个割集。Boruvka算法的关键在于如何判断最小权重边上的两个顶点是否处于同一割集中，一般使用并查集进行判断。