最小生成树算法、二分图

最小生成树

一、知识点

1.朴素版Prim算法对应稠密图（m和n²一个级别），堆优化版Prim算法对应稀疏图（m和n一个级别）。
2.Kruskal算法（适用于稀疏图）要先对所有边排序，时间复杂度为O(mlogm)，而m < n²，因此和O(mlogn)一个级别。
3.在写算法题时：

• 对于稠密图，使用朴素版Prim算法
• 对于稀疏图，使用Kruskal算法，堆优化版Prim算法一般不会用到。

二分图

一、知识点