Skip to content

最小生成树 MST

介绍

一个有 \(n\) 个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有 \(n\) 个结点，并且有保持图连通的最少的边，称作最小生成树 (Minimum Spanning Tree, MST) 。

最小生成树可以用 Kruskal（克鲁斯卡尔）算法或 Prim（普里姆）算法求出。

Kruskal 算法

假设 \(G=(V,E)\) 是一个含有 \(n\) 个顶点的连通网，则按照克鲁斯卡尔算法构造最小生成树的过程为：

  • 先构造一个只含 \(n\) 个顶点，而边集为空的子图，若将该子图中各个顶点看成是各棵树上的根结点，则它是一个含有 \(n\) 棵树的一个森林。
  • 之后，从网的边集 \(E\) 中选取一条权值最小的边，若该条边的两个顶点分属不同的树，则将其加入子图，也就是说，将这两个顶点分别所在的两棵树合成一棵树；
  • 反之，若该条边的两个顶点已落在同一棵树上，则不可取，而应该取下一条权值最小的边再试之。
  • 依次类推，直至森林中只有一棵树，也即子图中含有 \(n-1\) 条边为止。

Prim 算法

假设 \(G=(V,E)\) 是一个含有 \(n\) 个顶点的连通网，则按照 Prim 算法构造最小生成树的过程为：

  • 首先，定义 Vnew={x} ，其中 \(x\) 为集合 \(V\) 中的任一节点（起始点）；定义 Enew={} 。
  • 接着，在集合 \(E\) 中选取权值最小的边 \(<u,v>\)，其中 \(u\) 为集合 \(V_{new}\) 中的元素，而 \(v\) 不在 \(V_{new}\) 集合当中，且 \(v\in V\)（如果存在有多条满足前述条件即具有相同权值的边，则可任意选取其中之一）；将 \(v\) 加入集合 \(V_{new}\) 中，将 \(<u, v>\) 边加入集合 \(E_{new}\)中。
  • 重复以上步骤，直到 \(V_{new}=V\) 。
  • 最后，使用集合 \(V_{new}\) 和 \(E_{new}\) 来描述所得到的最小生成树。

注：部分资料来源于百度百科

Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.