用图建模关系

把对象抽象为顶点、关系抽象为边，many 现实问题化为图论问题。带权图上的核心算法：

最短路径与生成树

  • 最短路（Dijkstra）：导航、网络路由；
  • 最小生成树（Prim/Kruskal）：用最少成本连通所有点（管网、电网布线）。

网络流与关键路径

  • 最大流/最小割：管道、交通、供应链的吞吐瓶颈；
  • 关键路径 (CPM)：项目工期管理，找出决定总工期的任务链。

PageRank

网页是顶点、链接是边，按「重要网页指向的网页也重要」迭代，等价于马尔可夫链的平稳分布——把网络结构变成排名。

例题

例　给定城市间道路与距离，Dijkstra 逐步扩展最近顶点，求出起点到各城市的最短路与路径。

应用

网络模型用于交通导航、物流配送、通信网络、项目管理、社交网络分析、搜索引擎排名、供应链优化——凡涉及「连接与流动」皆可图建模。