最小生成树是图论中的一个概念。首先介绍一下什么是生成树。生成树就是将一个图中所有的顶点全部连接在一起，并且保证图中没有出现回路。
下图不是生成树，因为没有连接所有的顶点。
下图不是生成树，因为图中有回路。
像下图这样的才是生成树。
生成树的概念介绍完了。那么最小生成树的概念就比较明确了，这里的最小指的是所有的边权重之和最小。
下图是美国西雅图的自行车路线图，用的是最小生成树。
下图是随机生成的最小生成树，看起来非常像大自然的产物。最小生成树在自然界中比较常见。
原文：http://blog.csdn.net/caipeichao2/article/details/32340007
