最小生成树

1. 定义

设G=(V, E) 是无向连通带权图, E中每条边 (v, w) 的权为 c[v][w] . 如果 G 的一个子图 G' 是一棵包含 G 所有顶点的树, 则称其为 G 的生成树. 生成树上各边权的总和称为该生成树的耗费. 在 G 的所有生成树中, 耗费最小的生成树称为 G 的最小生成树.

核心目标: 用最小的总权重连接图中的所有顶点, 且不形成环路.

2. 构造算法

用贪心的思想来构建最小生成树.

3. Prim算法

从任一个点开始, 每次选取离当前树最近的一个新点加入, 直至把所有点都连进来.

4. Kruskal算法

把所有边按权重从小到大排序, 依次选择不形成回路的边, 直至只剩一个连通图为止.