一个有n个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有n个结点，并且有保持图联通的最少的边。在一个连通网的所有生成树中，各边的代价之和最小的那棵生成树称为该连通网的最小代价生成树（minimum cost spanning tree），简称为最小生成树。

许多应用问题都是一个求无向连通图的最小生成树问题。例如，要在n个城市之间铺设光缆，主要目标是要使这n个城市的任意两个之间都可以通信，但铺设光缆的费用很高，且各个城市之间铺设光缆的费用不同；另一个目标是要使铺设光缆的总费用最低。这就需要找到带权的最小生成树。

找连通网的最小生成树，经典算法有两种，普利姆（Prim）算法和克鲁斯卡尔（Kruskal）算法。