给定一个无向图，如果它的某个子图中任意两个顶点都互相连通并且是一棵树，那么这棵树就叫做生成树。如果边上有权值，那么使得边权和最小的生成树叫做最小生成树。
例如我们假设有这样一个图：把顶点看作村庄，边看作计划要修建的道路。为了在所有的村庄间通行，恰好修建村庄数目 - 1条道路时的情形就对应一颗生成树。修建道路需要投入建设费，那么求解使得费用最小的生成树就是最小生成树问题。
常见的求解最小生成树的算法有Kruskal算法和Prim算法。