写在前面,
要让一个n个顶点的图联通至少需要n - 1条边, 如何让这n - 1条边的权重之和最小就是最小生成树算法要解决的
二分图定义
如果一个图的所有顶点可被分为x和y两个集合, 并且所有边的两个顶点恰好一个属于x集合, 一个属于y集合,
(即每个集合内的顶点没有边相连)
啊哈算法详解 二分图总结
对于某些无向负权图不适用
- 对于下面这个图来说, 按照最小生成树算法, a-c这条边不会再加进去了, 但是实际上连通图最小的权值和, 加上这条边会更小。
无向正权图(边权之和随着边数的增加严格变大的图)
Orz
Otz