第2章 绘制行军地图：图的表示与存储

第 2 章 · 绘制行军地图：图的表示与存储

章节摘要：远征队认得了地形，接下来要把地图画下来——也就是把图存进计算机。同一个图至少有三种主流画法：邻接矩阵把连接情报填进方阵，查询飞快但吃内存；邻接表为每个顶点建一份邻居档案，省空间且遍历高效；边表则只记一张边清单，最适合流式处理与稀疏大图。本章把三种表示的代码实现、复杂度对比与选型原则讲透，因为后续每一场战役的时间复杂度，都直接由你选了哪种存储决定。

学习目标

阅读完本章，你应当能够：

1. 手写邻接矩阵与邻接表之间的互转代码，并处理有向、加权、多重边三种情况。
2. 说清"判断两点是否相邻"与"枚举某点的所有邻居"在两种表示下的复杂度差异。
3. 解释稀疏图为什么应该避开邻接矩阵，稠密图为什么可以放心用它。
4. 用邻接矩阵的幂计算"恰好经过若干条边的通路数"。
5. 面对百万级边数的图，做出合理的表示法选型并说明理由。

核心概念速览

金句：存储结构不是仓库，是武器的握把——握错了，再好的算法也使不上力。

子章节导航

第 1 节"邻接矩阵：方阵中的连接情报"从侦察情报的登记表讲起，给出矩阵表示的完整实现，并解锁它的隐藏技能：矩阵幂对应通路计数、布尔幂对应可达性。

第 2 节"邻接表：轻装远征的档案袋"解决矩阵的臃肿问题，用字典加列表为每个顶点建档。绝大多数图算法的默认驻地都在这里，本节还给出两种表示的空间实测对比。

第 3 节"边表、关联矩阵与表示法选型"补齐第三种画法，并给出一张面向实战的选型决策表——大规模图计算、图数据库、竞赛代码各有所好。

子章节之间的逻辑关系

一句话论点：三种画法没有优劣，只有与访问模式的匹配——你的算法怎么问问题，决定你该怎么存图。

  邻接矩阵 ──擅长──→ "这两点相连吗？"（查邻）
     │
     │  互转（各付一次遍历成本）
     ▼
  邻接表 ──擅长──→ "它的邻居都有谁？"（遍历）
     │
     │  摊开就是
     ▼
  边表   ──擅长──→ "把所有边排序/过滤/分批处理"（逐边作业）
​

前置知识与后续延伸

前置：第 1 章的图类词汇（尤其稠密与稀疏之辨）、Python 的字典与列表、一点复杂度记号的直觉（大写 O 记号在本章会反复出现，第 3 章再系统化）。

后续延伸：第 3 章的深度优先与广度优先搜索直接建立在邻接表上；第 5 章的 Floyd-Warshall 把邻接矩阵当作演算纸；第 6 章的 Kruskal 从排序边表起手。可以说本章是全册算法的军械库。

学习建议与选型心法

本章的落点不在"会写三种结构"，而在"会做选型判断"——这也是工程面试的高频考法。给你三个练手建议。第一，把互转代码当默写题：邻接矩阵转邻接表、邻接表转边表，每种转换都是一次双重循环，写熟了才能体会"转换本身也要付一次遍历的代价"，生产系统不会频繁互转的原因由此自明。第二，养成看复杂度倒推存储的习惯：读到某个算法声明"顶点数加边数"的复杂度，就应意识到它默认邻接表、且按"枚举邻居"计价；读到顶点数平方的声明，就应嗅到矩阵演算的味道——存储与算法是连体账单，这条本章正文反复强调的线索，值得你拿第 5 章的三个算法再验证一遍。第三，动手跑一次空间实测：正文第二节给出的内存对比代码，把顶点数改大一档再跑，亲眼看方阵字节量的平方级增长——数字的冲击比任何论述都管用。自测标准：面对一个新场景（比如"社交平台存十亿用户的好友关系，主要操作是查某两人是否好友"），你能给出表示法选择并说出两条理由，本章就算通关。