最小生成树（无向图）+ 二分图分类与总结主要内容

  • 一、最小生成树
    • 1、Prim 算法（普利姆算法）
    • 2、Kruskal 算法（克鲁斯卡尔算法）
  • 二、二分图
    • 1、染色法
    • 2、匈牙利算法

一、最小生成树

1、Prim 算法（普利姆算法）

  • 分类：
    • 朴素版Prim算法（最小生成树的稠密图使用）：O（n^2）
    • 堆优化版 Prim 算法（稀疏图，但是不常用，一般用 kruskal 算法）：O（mlogn）
  • 特点：与 Dijkstra 算法类似（使用剩下点中，距离最小的点进行更新），而 Prim 算法使用的是距离集合最小的边进行更新。

2、Kruskal 算法（克鲁斯卡尔算法）

  • 特点：
    • 最小生成树（总路径最短问题）+ 稀疏图 常用算法
  • 复杂度：
    • O（mlogm）固定，与点数无关

二、二分图

1、染色法

  • 特点：
      1. 主要目的是进行是否是二分图的判别工作，主要依据是不存在的奇数环
      1. 使用 DFS 进行深搜
  • 复杂度：
    • O（n + m）

2、匈牙利算法

  • 特点：
    • 解决二分图的算法，又称渣男算法，主要解决二分图两个集合之间的最大匹配对数问题
  • 复杂度：
    • 最坏是 O（mn），但是实际运行时间远小于O（mn）