图论总结


最短路

各种最短路算法的适用情况及时间复杂度如下:

存在负权边,或者判定负环,推荐用SPFA算法。
对最短路的边数存在限制,则只能使用Bellman Ford算法。

最小生成树

最小生成树的算法及其时间复杂度如下:

堆优化版的prim算法几乎不会用到,Kruskal算法的时间复杂度与其近似,思路与代码实现都更优。

二分图

二分图的相关算法及时间复杂度如下:


文章作者: Kong Aobo
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 Kong Aobo !
  目录