数据结构-图入门（最短路与最小生成树）

发表于 分类于

图用于描述“多对多”关系，比如地图、社交网络、依赖关系。

图的基本概念

  • 顶点（Vertex）
  • 边（Edge）
  • 有向图 / 无向图
  • 带权图

经典问题

  • 最短路径：Dijkstra、Floyd、SPFA
  • 最小生成树：Prim、Kruskal
  • 依赖排序：拓扑排序

场景例子

  • 导航：最短路径
  • 组网布线：最小生成树
  • 构建系统任务编排：拓扑排序