[第 二十五节] 贪心算法 最小生成树问题

1、问题描述

考虑一个无向连通赋权图 G = (V, E) ，即一个网络系统 E 中每一条边 (u, v) 的权重记为 c[u][v] 。若 G 的某个子图 T 包含所有顶点且形成一棵树，则称 T 为 G 的 最小生成森林 。而所有可能产生这样结构下的最轻量级连接方案则被称为该图 G 的 最小支撑森林 。

在网络中广泛使用的最小生成树不仅在理论上有重要价值，在实践中也具有广泛的用途。例如，在规划一个高效的通信网络系统时，我们可以将各个节点定义为具体的地理位置（如城市），将连接不同节点之间的线路抽象为带权值的边（即边(v,w)具有权重c[v][w]）。通过计算这些节点间的最小生成树，则能够得出构建该通信网络体系时所采用的最低成本策略。

2、MST性质

设G=(V,E)为连通加权图，则当(u,v)∈E时若u∈U且v∈V-U，在所有满足该条件的边中若(u,v)具有最小权重c[u][v]则必定存在包含这条边的一棵最小生成树这一特性通常被称作 MST属性 。

MST特性的一种证明方法：如下图所示, 假设G中不存在任何一颗最小生成树包含边(u, v). 将该边加入到G的一个最小生成树T中, 这将会形成一个包含边(u, v)的环. 在这个环上必定存在一条不同于u-v的路径u'-v', 使得u'属于U集合而v'属于V-U集合