图论是 CSP-S 的核心考点。本文用通俗语言讲清楚。

什么是图

图 = 点 + 边。就像地铁线路图。

图的分类

  • 无向图：边没有方向
  • 有向图：边有方向
  • 带权图：边有"距离"

图论经典算法

遍历

  • DFS（深度优先）
  • BFS（广度优先）

最短路

  • Dijkstra
  • Floyd

最小生成树

  • Kruskal
  • Prim

咨询图论学习：151 6522 2880