图论：

**生成树问题： **

• 最小生成树
  • 次小生成树(非严格/严格)
  • 瓶颈生成树
  • kruscal重构树
• 最小树形图
• 最小直径生成树

树上问题:

• 基础性质 (直径,重心)
• 最近公共祖先(LCA)
• 树上启发式合并(dsu on tree)
• 虚树
• 树链剖分
  • 重链剖分
  • 长链剖分
• 树分治:
  • 点分治
  • 边分治
  • 点分树
  • 动态树分治
• 树同构:
  • AHU
  • 树哈希

最短路问题：

• Johnson 全源最短路径算法
• 分层图最短路
• k短路
• 同余最短路
• 差分约束

连通问题:

• 强连通分量

• 双连通分量

• 割点和桥

• 圆方树

• 2-SAT

特殊图问题:

• 欧拉图
• 哈密顿图
• 二分图
  • 图的着色
• 平面图

特殊应用:

• 斯坦纳树
• 矩阵树定理