概念

给定一个带权的无向连通图，如何选取一棵生成树，使得树上所有边上权的总和为最小，就是最小生成树（Minimum Cost Spanning Tree，简称 MST）。

说得通俗一点，一个具有 n 个结点的带权图，使用 n-1 条边把各个结点连起来并使得李静上所有权值的和最小，如下图中的粗线所示。

求最小生成树主要有两种算法：普利姆算法和克鲁斯卡尔算法。

普利姆算法

克鲁斯卡尔算法