从无向图的角度讲,对于一个联通的无向图,我们可以构造出这个无向图的一棵生成树.形式化地说,一棵给定无向图$G=(V,E)$的生成树$S$是一个图$(V,E‘)$,满足
1) $S$联通.
2) $S$中不存在环.
我们可以定义边的权值$w(E)$,一般来说,$w(E)$的值相对边是独立的(互不影响)的.一棵生成树的权值$w(T)$就是它的边的权值和.最小生成树,就是使$w(T)$最小的生成树$T\in g(G)$.
原文：http://www.cnblogs.com/tmzbot/p/4603215.html