最小生成树（min spanning tree）

概念

带权连通图中代价最小的生成树

以上的基本原则是基于MST的如下性质： 设G=(V，E)是一个带权连通图，U是顶点集V的一个非空子集。若u∈U ，v∈V-U，且(u, v)是U中顶点到V-U中顶点之间权值最小的边，则必存在一棵包含边(u, v)的最小生成树。

证明： 用反证法证明。 设图G的任何一棵最小生成树都不包含边(u,v)。设T是G的一棵生成树，则T是连通的，从u到v必有一条路径(u,…,v)，当将边(u,v)加入到T中时就构成了回路。则路径(u, …,v)中必有一条边(u’,v’) ，满足u’∈U ，v’∈V-U 。删去边(u’,v’) 便可消除回路，同时得到另一棵生成树T’。 由于(u,v)是U中顶点到V-U中顶点之间权值最小的边，故(u,v)的权值不会高于(u’,v’)的权值，T’的代价也不会高于T， T’是包含(u,v) 的一棵最小生成树，与假设矛盾。

PRIME算法

从空集S开始，选点，初始时用一个数组costMin[v]记录每个点到S集合的cost,c初始化为正无穷。并随机选择一个点加入，更新costMin[v]到S的cost. 之后每次在不属于S的集合中选一个加入S集合代价costMin[v]最小的点。直到所有的点都加入。

克鲁斯卡尔

选边，每次选最小的边， 并且这个边的两个节点不能是本来就在一个连通图中的。