《最小生成树》，此词条收录于06/28，仅供参考
最小生成树其实是最小权重生成树的简称。一个有n个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有n个结点，并且有保持图连通的最少的边。最小生成树可以用kruskal（克鲁斯卡尔）算法或Prim（普里姆）算法求出。最小生成树性质：设G=(V，E）是一个连通网络，U是顶点集V的一个非空真子集。根据树的定义，则T中必有一条从红点u到蓝点v的路径P，且P上必有一条紫边（u，v）连接红点集和蓝点集，否则u和v不连通。当一条边（u，v）加入T时，必须保证T∪(u，v)仍是MST的子集，我们将这样的边称为T的安全边。
