元数据卡

• 前置知识：第5章 关系与函数
• 预计时间：50 分钟
• 核心难度：进阶
• 完成标志：掌握图的表示方法，理解图的遍历与连通性，了解最短路径思想

你的进度

上一座塔学会了计数。组合塔的第二间，墙上全是点和线交织的图案。馆长用手指沿着一条路线划过："从一个点到另一个点，有几条路？这是地图的数学。"

你的任务

社交网络中"朋友的朋友"是怎么找到的？地图 App 的导航路线是如何计算的？调度系统中任务依赖关系如何建模？这些问题共享同一个数学结构——图。它不过是"节点"和"边"的集合，却能描述互联网拓扑、程序的控制流、CI/CD 的管道依赖、状态机的全部转移。

本章分层

• 必读：图的定义与表示，深度/广度优先搜索，最短路径
• 选读：最小生成树，拓扑排序

破局 · 溯源

你需要安排一个项目的构建顺序。模块 A 依赖 B, B 依赖 C, D 依赖 B 和 E。你要找出"先编译哪个"的顺序，还要知道"能不能编译一些"。手工排了十分钟，发现可能死锁了。这时候你需要一个系统的方法——图论提供的拓扑排序。

图的定义：图 G = (V, E)，其中 V 是节点（顶点）集合，E 是边集合。一条边连接两个节点。

概念	定义	编程对应
有向图	边有方向，a→b≠b→a	函数调用关系
无向图	边无方向	社交网络朋友关系
带权图	边上有数值（权重）	地图道路距离
邻接矩阵		V
邻接表	每个节点关联一个邻居列表	稀疏图（大多数实际场景）

选择的存储方式影响算法效率。大多数实际图的边数 E 远小于节点数 V 的平方（稀疏图），此时邻接表的内存和遍历效率都远优于邻接矩阵。

图的遍历：访问图中所有节点的方式。

深度优先搜索（DFS）：沿着一条路走到黑，走不通再回头。递归实现天然匹配：

DFS(v):
  标记 v 已访问
  对于 v 的每个邻居 u:
    如果 u 未访问则 DFS(u)

DFS 在拓扑排序中很有用——后序遍历的顺序即是拓扑序的逆序。

广度优先搜索（BFS）：一层一层向外扩散。用队列实现。BFS 找出的路径一定是最短路径（在无权图中）。

BFS(s):
  初始化队列 Q, 将 s 入队
  标记 s 已访问
  while Q 非空:
    v = Q.dequeue()
    对于 v 的每个邻居 u:
      如果 u 未访问则标记并入队

最短路径：在有权图中，Dijkstra 算法是基准。从起点开始，维护到每个节点的当前最短距离，用优先队列选择当前距离最小的未处理节点。

拓扑排序：对有向无环图（DAG）的节点排序，使得每条边的起点都在终点之前出现。如果图中存在环（循环依赖），拓扑排序不可行——你的构建系统会报错。

常见陷阱

• 忘记检查图是否有环。DFS 和 BFS 在无环图上跑得很开心，遇到环就无限循环。遍历前需要检测环。
• 混淆稀疏图和稠密图的算法选择。邻接矩阵上 O(V²) 的 Dijkstra 在稠密图上更快，邻接表 + 优先队列的 O(E log V) 在稀疏图上更快。没有绝对最优。
• 认为图是"计算机科学才有的"。图论的起源——柯尼斯堡七桥问题——比计算机早了两百多年。

通关挑战

• 画出你的项目构建依赖的 DAG，给出拓扑排序结果。
• 对同一个图分别用 DFS 和 BFS 遍历，对比输出顺序的差异。
• 在 Python 中用邻接表实现一个无向图，并编写 is_connected() 方法判断连通性。

旅人笔记

图是把关系画出来的数学。节点是你关心的实体，边是它们之间的联系。遍历、连接性、排序——这是你在社交网络、地图、构建系统中每天都在处理的底层模型。

→ 下一站预告：图给了你关系的结构。但如果这些关系不是确定的呢？"明天下雨的概率是 70% "——下面进入概率的领域。