最小生成树学习方法Prim&Kruskal

最小生成树快速入门【Prim&Kruskal】

1 何为最小生成树？

要理解最小生成树的概念，可能需要首先掌握生成树的定义。

生成树（Spanning Tree）：指的是在某一无向图中，由图中全部V个顶点和V-1条边构成的子图，并且该子图本身是连通的（此处设V表示图中的节点总数）。

而所谓的最小生成树（Minimum Spanning Tree，简称MST），则是所有生成树中具有总权值最小特征的那棵生成树。

2 何以求解最小生成树？

求解最小生成树 的常用方法涵盖 普里姆算法（Prim’s Algorithm）、克鲁斯卡尔算法（Kruskal’s Algorithm）以及索尔连科算法（Borůvka’s Algorithm）。这些技术在不同场景下表现出不同的性能特征和适用范围，简要总结如下：

1. 普里姆算法 (Prim’s Algorithm) ：
   • 对于边权重分布不均 的图具有较好的适应性。
   • 从图中的一个顶点 出发，持续扩展新的边与顶点，直至构造出完整的最小生成树。
   • 在每一步中，优先选取连接已构建顶点集合与未选顶点集合之间权重最低的边。
   • 算法的时间复杂度为 O(E