跳转至

图论

代码实现

概念

  • 稠密图:边数 接近或等于完全图,反之为稀疏图。

常见算法

  • 拓扑排序
  • 二分图匹配匈牙利算法
  • 单源非负最短路径 Dijstra 算法
  • 最小生成树的 Prim 算法(思路类似于 Dijkstra;适用于稠密图。)
  • 最小生成树的 kruskal 算法(将边按长度排序,依次裁决每条边是否符合条件。)