【图论2-3】最小生成树

试想在一个平原国家中有若干城市，要建立若干高速公路，这些高速公路可以建成直线，连 接在两个城市之间。如何规划这些高速公路使建造距离总和最短，就是一种典型的最小生成树问 题。 树是一种特殊的图，具有很多特殊的性质。生成树问题研究的是将图中的所有顶点保留，但 只选择图中的部分边，得到一棵树（也就是图的生成树）的问题。最小生成树则是在这些生成树 中，边权之和最小的生成树。可以使用 $Prim$ 算法或者 $Kruskal$ 算法求解最小生成树。 对应进阶篇第 11 章。