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