最小生成树--MST性质

例子:

6个顶点,10条边,假设U子集中只有一个顶点v1,那么剩下的差集V-U,在所有的顶点中减去v1,在、这5个顶点就在V-U集合中

从u到v有边,有哪几条边?v1到v2的,v1到v3,v1到v4的三条边,其中v1到v3是最小的,这条边的权值是1,即存在权值最小的边,必然包含在最小生成树里头;反过来,我们把权值最小的边包含在最小生成树里头,构造问题就解决了

接下来,详细看MST性质的解释:

n个顶点即V集合,可以分成两个集合,一个是U,已经在生成树上的集合;另一个是V-U

接下来就选权值最小的边