图系列第 3 篇：图的存储——邻接矩阵、邻接表与边集

嘿，我们又见面了。这是图系列的第三篇文章。如果你从第一篇一路读到这里，先给自己鼓个掌：你已经知道图是什么了——顶点是对象，边是对象之间的关系；你知道边可以带方向、可以带权重；你知道”度”怎么数，知道路径和环意味着什么，也知道连通分量和强连通说的是什么。今天我们要做的事，是把这些概念从纸上搬进计算机的内存里。

先快速回顾一下前两篇，因为我们马上要站在它们肩上。

第一篇《图的基本概念》讲了图的两块积木：顶点（Vertex）和边（Edge）。顶点是图里的”对象”，边是对象之间的”关系”。地图上，路口是顶点、道路是边；社交网络里，人是顶点、好友关系是边；课程表里，课程是顶点、先修关系是边。我们还学了四种分类：边不分方向的叫无向图，边分方向的叫有向图；边上带数字的叫带权图，不带数字的叫无权图。然后我们学习了”度”：无向图里一个顶点连了几条边，它的度就是几；有向图里还要分出度（从它出发的边）和入度（指向它的边）。最后我们认识了握手定理：无向图所有顶点的度之和，恰好等于边数的两倍，因为每条边都会给它的两个端点各贡献一度。

第二篇《路径、环与连通性》把图从”静态的照片”变成了”可以走的路网”。路径是沿着边走出的顶点序列；如果一条路径的起点和终点是同一个顶点，并且中间至少有一条边，它就是一个环。两个顶点之间只要有路径，我们就说它们连通；无向图里所有顶点两两连通，就叫连通图；一张不连通的图可以拆成若干个连通分量，每个分量内部互相连通，分量之间则”老死不相往来”。有向图更讲究，从 u 能到 v、从 v 也能到 u，才叫强连通；强连通分量就是有向图里”彼此都能到达”的极大集团。

前两篇我们一直在纸上画图：画圆圈当顶点，画线当边，数字标在边上。画图当然很直观，可你稍微想一下就会意识到一个问题——计算机没有纸，也没有眼睛。它只有内存，内存里放的是字节、数组、对象、字符串、数字。那么问题来了：一张图到底该怎么”装”进程序里？这就是本篇要解决的核心问题。

第 1 章 问题：图是概念，程序里要用数据结构装

1.1 从”画图”到”存图”：同一张图，不同的装法

先想清楚我们到底要存储什么。一张图由两部分组成：顶点集合和边集合。顶点集合本身不难存——给每个顶点一个编号（0、1、2……），再准备一个数组或者一个对象，把顶点附带的信息（名字、坐标、城市人口之类）存进去就行。真正考验设计的是边集合：边是”两个顶点之间的关系”，而关系不是一串连续的字节，它散落在顶点之间，像一张网。怎么把这面网编成线性、规整、机器能读的数据，就是”图的存储”要回答的问题。

你可能已经隐约感觉到，同一张图可以有完全不同的装法。就像同样一份通讯录，有人喜欢按姓名排成一张大表，有人喜欢每人一个名片盒、名片上写满联系方式，还有人喜欢把每一条联系记录单独抄在小卡片上按日期归档。三种装法保存的信息一模一样，但”查某个人的电话”和”统计本月新增联系人数”这两种操作的速度会完全不同。图的存储也是这个道理：信息量相同，性能天差地别，关键看你之后要对图做什么。

为了避免空谈，我们约定一套贯穿全文的”词汇表”。以后说到一张图，默认它一共有 V 个顶点（V 是顶点数 Vertex 的首字母）、E 条边（E 是边数 Edge 的首字母）。如果带权重，就用 w(u, v) 表示从 u 到 v 那条边的权重，比如距离 5 公里、票价 30 元、带宽 100 Mbps。本章后面给出的所有复杂度，都会用 V 和 E 这两个字母来表达，你只要记住两条直觉：V 决定”顶点这边”的规模，E 决定”边这边”的规模。

还要约定三种最常用的操作，因为三种存储方案的区别，本质上就是这三种操作上的区别：

第一，查边（hasEdge）。给定两个顶点 u 和 v，问一句”u 和 v 之间有没有边？“如果没有边，通常还要顺带回答”这条边的权重是多少”。这是图论问题里最常见的查询，最短路径算法、传递闭包、连通性判断都会用到它。

第二，遍历邻居（neighbors）。给定一个顶点 u，把 u 的所有邻居一个个拿出来处理。深度优先搜索（DFS）、广度优先搜索（BFS）、Dijkstra 最短路、拓扑排序，几乎一切”从某个点向外扩散”的算法，核心操作都是遍历邻居。这个操作做得快不快，直接决定算法快不快。

第三，遍历所有边（allEdges）。把图中每一条边都过一遍，有时还要求按某种顺序过。最小生成树里的 Kruskal 算法要按权重从小到大处理所有边，Bellman-Ford 最短路径算法要反复把每条边”松弛”一遍，它们的核心操作就是遍历所有边。

你记住这三板斧：查边、遍历邻居、遍历所有边。接下来我们介绍的三种存储方案，就是分别在这三件事上各有千秋。邻接矩阵让查边快到极致，邻接表让遍历邻居快到极致，边集数组让”把全部边捞出来、排序、一条条处理”变得最直接。没有一种方案是十全十美的，选择存储方式，就是选择你愿意为哪种操作付出代价。

1.2 三种方案，先见个面

在深入细节之前，先让三位主角登个场，你有个整体印象，后面读起来会轻松很多。

第一位是邻接矩阵（Adjacency Matrix）。它用一个大方阵来存图：方阵的行和列都对应顶点，第 i 行第 j 列的格子就记录”顶点 i 到顶点 j 有没有边、权重是多少”。它的思路非常朴素——所有顶点两两之间的关系，我全部预留一个位置，一格不多，一格不少。代价是空间永远要按”顶点数的平方”来准备，哪怕图中根本没有多少条边。

第二位是邻接表（Adjacency List）。它反过来想：既然大多数图里，每个顶点只和少数几个顶点相连，那我为每个顶点单独开一张小列表，只记录”它真正连着的那些邻居”不就行了？每条边只出现一次（有向图）或两次（无向图），空间和边数成正比。代价是”u 和 v 有没有边”这个问题，不能一眼看出答案，得在 u 的邻居列表里找一找。

第三位是边集数组（Edge List / Edge Array）。它干脆连”顶点配列表”这层结构都不要了，直接把所有边平铺成一个数组，每一条边占一条记录，记录里写着 u、v 和权重 w。它是最”扁平”的存法，最适合”把边拎出来按权重排序、逐条处理”的算法，比如最小生成树的 Kruskal 算法——这会在图系列后面的章节里派上大用场。

用一张图把三位主角的关系画出来，大概是这样的：

flowchart LR
    G[同一张图] --> M[邻接矩阵<br/>大方阵，查边最快]
    G --> L[邻接表<br/>每人一列表，遍历邻居最快]
    G --> E[边集数组<br/>边平铺，排序处理最方便]

如果你手边有我们配套的图论实验室，建议现在就把这张小图拖进去玩一玩：同一个图，切换成矩阵、表、边列表三种视图，你会直观看到”同一条边在不同装法里的位置”。玩过之后，再往下读，每一句复杂度分析都会变得特别实在。

别急着背这张图。下面每一章我们都会用同一个具体例子把对应方案讲透，最后再放到一起对比。

1.3 贯穿全文的小例子：一张稀疏图

为了不让你在抽象符号里打转，我准备了一张小图，后面讲邻接表和边集数组时都会用到它。它一共有 6 个顶点，我偷懒用数字 0 到 5 给它们编号；一共有 7 条带权无向边：

边	权重
0—1	4
0—2	2
1—2	3
1—3	5
2—4	6
3—5	1
4—5	8

画出来长这样：

flowchart LR
    0 ---|4| 1
    0 ---|2| 2
    1 ---|3| 2
    1 ---|5| 3
    2 ---|6| 4
    3 ---|1| 5
    4 ---|8| 5

你可以先手动数一数每个顶点的度：顶点 0 连了 1 和 2，度是 2；顶点 1 连了 0、2、3，度是 3；顶点 2 连了 0、1、4，度是 3；顶点 3 连了 1、5，度是 2；顶点 4 连了 2、5，度是 2；顶点 5 连了 3、4，度是 2。把所有度加起来：2 + 3 + 3 + 2 + 2 + 2 = 14，正好是边数 7 的两倍，握手定理在这里又一次应验了。

这张图 6 个顶点、7 条边，平均每个顶点只跟 14 ÷ 6 ≈ 2.3 个邻居相连，是一张典型的稀疏图（Sparse Graph）。什么叫稀疏？通俗地说，就是”顶点很多，但每个顶点真正连到的邻居很少”。与它相对的叫稠密图（Dense Graph），顶点之间几乎两两相连，边数接近”能连的最大值”。我们会发现：稀疏图和稠密图，适合的存储方案是不一样的——这正是本章最核心的结论之一。

好了，铺垫完毕。接下来我们从最直观、最好懂的邻接矩阵开始。

第 2 章 邻接矩阵：用一张大方阵装下所有关系

2.1 定义：A[i][j] 就回答”i 到 j 有没有边”

邻接矩阵的想法简单到近乎粗暴：我不管你的图里到底有几条边，先按照”任意两个顶点都可能相连”的最高标准，把所有顶点两两配对的位置全部预留出来。具体做法是开一个 V 行 V 列的二维数组 A，其中第 i 行第 j 列的元素 A[i][j] 专门用来记录”顶点 i 到顶点 j 之间的边”。

如果是无权图，A[i][j] 就填 0 或 1：1 表示 i 到 j 有边，0 表示没有。如果是带权图，A[i][j] 就填这条边的权重，比如 5 表示权重为 5；没有边的地方不能填 0，因为 0 可能被误认为”一条权重为 0 的边”，所以惯例是填一个”无穷大”，在代码里通常用 Infinity、Number.MAX_SAFE_INTEGER 或者一个很大的常数（比如 10^9）来表示”此路不通”。

还有一个细节：顶点自己到自己的对角线 A[i][i] 怎么填？在没有自环的普通图里，习惯上填 0——“从自己到自己不用走任何边，代价是 0”。这个约定在最短路径算法里特别重要：Floyd-Warshall 算法初始化时把对角线设成 0，就表示”原地不动是免费的”。如果图允许自环（从某个顶点出发又回到它自己的边），那 A[i][i] 就如实填 1 或对应权重；不过我们后面讨论的图，默认没有自环，除非特别说明。

有了这个定义，很多问题都变得”一翻即知”。查边 u—v：直接看 A[u][v] 这一个格子，O(1) 时间，快到极致。求顶点 u 的度：数一数第 u 行（或第 u 列）里有多少个非零/非无穷的格子，O(V) 时间。整个图的边数：把矩阵里所有有边的格子数一遍，O(V²) 时间——注意，即使你只想数边，也必须把整个方阵扫一遍，因为边是”散落”在方阵各处的。

2.2 无向图的矩阵是对称的：半个矩阵就够了

无向图有个非常漂亮的性质：边不分方向，u—v 和 v—u 是同一条边。反映在矩阵上，就是 A[u][v] 永远等于 A[v][u]——矩阵关于主对角线对称。你看矩阵的时候，会发现上半部分和下半部分是”镜像”，左边和右边一一对应。

这个性质带来两个实际好处。第一，如果你存的是无向图，理论上只需要存上三角（或下三角）一半就够了，能省一半空间；不过工程上为了代码简单、下标访问快，绝大多数实现还是存完整的 V×V 矩阵，多出的那一半空间当作”买省心”。第二，填边的时候有个很容易犯的错误：只写了 A[u][v] = w，忘了写 A[v][u] = w，结果图变得”半通不通”——从 u 能查到 v，从 v 却查不到 u。记住这个对称性，写代码时务必两边都填。

有向图就没有这个福利了。u→v 有边不代表 v→u 有边，所以 A[u][v] 和 A[v][u] 是两个完全独立的格子，各填各的，矩阵一般不再对称。

为了把矩阵讲具体，我换一张更”稠密”的小图。它有 4 个顶点：0、1、2、3，任意两个顶点之间都有带权边，一共 6 条边——你回忆一下，4 个顶点的无向图最多能有多少条边？C(4,2) = 6，所以这是一张”满配”的完全图，也是稠密图的极端代表。

flowchart LR
    0 ---|3| 1
    0 ---|1| 2
    0 ---|7| 3
    1 ---|2| 2
    1 ---|5| 3
    2 ---|4| 3

这张图存成邻接矩阵，就是下面这个 4×4 方阵。行是”起点”，列是”终点”，第 i 行第 j 列的格子是”从 i 到 j 的权重”；没有边的地方填 ∞，对角线填 0：

flowchart TB
    subgraph r0[第 0 行]
        m00["0"] ~~~ m01["3"] ~~~ m02["1"] ~~~ m03["7"]
    end
    subgraph r1[第 1 行]
        m10["3"] ~~~ m11["0"] ~~~ m12["2"] ~~~ m13["5"]
    end
    subgraph r2[第 2 行]
        m20["1"] ~~~ m21["2"] ~~~ m22["0"] ~~~ m23["4"]
    end
    subgraph r3[第 3 行]
        m30["7"] ~~~ m31["5"] ~~~ m32["4"] ~~~ m33["0"]
    end

请你对照着检查两件事。第一，沿主对角线看，4 个格子全是 0。第二，沿着对角线”对折”，左上角和右下角的数字一一相等：m01 是 3，m10 也是 3；m02 是 1，m20 也是 1；m13 是 5，m31 也是 5。这就是无向图矩阵的对称性，你在纸上亲手折一次，比背十遍都管用。

2.3 空间代价 O(V²)：为什么”大方阵”不是免费的

邻接矩阵最大的代价，就是空间永远按 V² 增长，跟实际边数 E 完全无关。哪怕你的图只有一条边，只要它有 V 个顶点，矩阵就必须准备 V×V 个格子；哪怕你的图有 100 万条边，只要 V 不变，矩阵还是 V×V 个格子，不多不少。

我们来做一道算术题，体会一下 V² 有多吓人。假设每个格子用一个 4 字节的整数存权重：

当 V = 1000 时，矩阵有 100 万个格子，占 4 MB，完全没问题；

当 V = 10000 时，矩阵有 1 亿个格子，占 400 MB，已经比较吃力了；

当 V = 100000 时，矩阵有 100 亿个格子，占 40 GB，普通电脑根本装不下。

注意，10000 个顶点在真实世界里一点都不算多——一张城市地图的路口就有几万个，一个社交平台的好友图则有几亿个顶点。所以邻接矩阵的适用面其实很窄：它只适合顶点数较小、或者图本身非常稠密的场景。工程上，当 V 达到几万级别时，邻接矩阵基本就被淘汰了，不管图有多稠密都很难扛住内存。

顺带一提，如果你存的是无向图，只存上三角可以把内存减半；如果矩阵元素只是 0/1（无权图），还能用位图（每一位代表一个格子）进一步压缩成 V²/8 字节。这些是优化手段，思路都是”矩阵结构不变，省格子”。但省来省去，V² 的增长曲线没有变，当 V 变大时照样指数式膨胀。

2.4 稠密图场景：矩阵什么时候才划算

既然矩阵这么”费内存”，它存在的意义是什么？答案是：当图本身足够稠密时，浪费就变成了”物有所值”。

先看什么算稠密。V 个顶点的无向图，最多有 V(V-1)/2 条边；有向图最多有 V(V-1) 条边（不算自环）。如果一张图的边数 E 接近这个上限，也就是 E 的量级达到 O(V²)，它就是稠密图。稠密图里，每条边”平均”占用矩阵中的一个有效格子，矩阵的格子利用率接近 50%（无向图只用到一半），浪费可以接受。反过来，如果 E 只有 O(V) 的量级，矩阵里 99% 的格子都是 ∞，那就是用 100 平方米的豪宅装一件行李，纯属浪费。

除了图本身稠密，还有两类场景特别喜欢矩阵。第一类是以”查任意两点之间的边”为高频操作的算法，最典型的就是 Floyd-Warshall 全源最短路径：它的三层循环要反复查询 A[i][k] + A[k][j]，如果换成邻接表，每次查询都要遍历列表，算法复杂度会直接劣化。第二类是图论证明和理论研究：矩阵是”二维表格式”的结构，数学家们可以把它当线性代数对象来运算，比如矩阵的 k 次幂 A^k 的 (i,j) 元素恰好等于”从 i 到 j 长度恰好为 k 的路径条数”——这个结论在邻接表或边集里很难自然表达。

所以邻接矩阵的黄金场景可以概括为：顶点数不大（几千以内）的稠密图，或者算法要求高频”查边”（如 Floyd、传递闭包）。记住这两个条件，你就能准确判断什么时候该用矩阵。

2.5 三种操作在矩阵上的账本

我们把 1.1 节约定的三种操作，在邻接矩阵上逐一算账：

查边 hasEdge(u, v)：直接读 A[u][v]，O(1)。这是矩阵的看家本领，没有其他方案能比它更快；

遍历邻居 neighbors(u)：必须把第 u 行从头扫到尾，逐格判断有没有边，O(V)。即使 u 只有 1 个邻居，也要看 V 个格子；

遍历所有边 allEdges()：把整个矩阵扫一遍，O(V²)。对稠密图来说 V² ≈ 2E，还算划算；对稀疏图来说，V² 远大于 E，非常亏。

另外补两个常用统计：无向图中顶点 u 的度 = 第 u 行非零元素个数；有向图中 u 的出度 = 第 u 行非零个数，入度 = 第 u 列非零个数。这些统计都是 O(V)。

2.6 用代码把矩阵写出来

下面用 TypeScript 实现一个最常用的版本：带权无向图的邻接矩阵。我会把”无边用 Infinity 表示”这个约定写进代码里，这样最短路径算法可以直接拿它当输入。

// 带权无向图的邻接矩阵实现
class WeightedUndirectedGraphMatrix {
  private matrix: number[][];

  constructor(private vertexCount: number) {
    // 初始化 V×V 矩阵，全部填 Infinity，表示"无边"
    this.matrix = Array.from({ length: vertexCount }, () =>
      Array(vertexCount).fill(Infinity)
    );
    // 对角线填 0：自己到自己的代价是 0
    for (let i = 0; i < vertexCount; i++) {
      this.matrix[i][i] = 0;
    }
  }

  // 添加无向边 u—v，权重为 w
  addEdge(u: number, v: number, w: number): void {
    // 无向图对称：两边都要填
    this.matrix[u][v] = w;
    this.matrix[v][u] = w;
  }

  // 查询 u—v 是否有边；没有边返回 false
  hasEdge(u: number, v: number): boolean {
    return this.matrix[u][v] !== Infinity;
  }

  // 查询边权；无边返回 Infinity
  getWeight(u: number, v: number): number {
    return this.matrix[u][v];
  }

  // 遍历邻居：返回 [邻居顶点, 权重] 的列表
  getNeighbors(u: number): Array<[number, number]> {
    const result: Array<[number, number]> = [];
    for (let v = 0; v < this.vertexCount; v++) {
      if (this.matrix[u][v] !== Infinity && u !== v) {
        result.push([v, this.matrix[u][v]]);
      }
    }
    return result;
  }

  // 无向图：u 的度就是第 u 行里有效边的个数
  degree(u: number): number {
    let d = 0;
    for (let v = 0; v < this.vertexCount; v++) {
      if (this.matrix[u][v] !== Infinity && u !== v) d++;
    }
    return d;
  }
}

// 使用示例：构造第 2 章的 4 顶点完全图
const g = new WeightedUndirectedGraphMatrix(4);
g.addEdge(0, 1, 3);
g.addEdge(0, 2, 1);
g.addEdge(0, 3, 7);
g.addEdge(1, 2, 2);
g.addEdge(1, 3, 5);
g.addEdge(2, 3, 4);

console.log(g.hasEdge(0, 3)); // true
console.log(g.getWeight(0, 3)); // 7
console.log(g.getNeighbors(2)); // [[0,1],[1,2],[3,4]]

如果你存的是无权图，把 Infinity 换成 0、把权重换成 1 即可，其他逻辑完全一样。如果你存的是有向图，只要把 addEdge 里对称填写的两行删掉一行，只写 matrix[u][v] = w，矩阵就不再对称，查边和统计入度/出度的代码也相应调整为只读行或只读列。

2.7 矩阵的三个变体：布尔矩阵、距离矩阵与可达矩阵

邻接矩阵的魅力在于”同一个方阵，换个填法就是另一种数据结构”。工程和算法里最常见的有三个变体，它们长得一模一样，含义却不同，别搞混。

第一个是布尔矩阵（也叫 0-1 矩阵）：格子只填 0 或 1，1 表示有边，0 表示没有。它用于无权图，也是”邻接矩阵的布尔化”。布尔矩阵在计算传递闭包（判断任意两点之间是否存在路径）时特别好用：反复做”逻辑或 + 逻辑与”的矩阵乘法，最终得到可达矩阵——这个演算过程在线性代数里非常漂亮，但代码实现时通常直接用 Floyd 思路，没必要真做矩阵乘法。

第二个是距离矩阵：格子里直接填两点之间的边权，没有边填 ∞，对角线填 0。这就是我们在 2.6 节代码里实现的版本。Floyd-Warshall 算法会在距离矩阵上原地更新：不断用”经过中转点 k 的路径”去比较”当前已知路径”，把更短的距离写回格子。算法结束时，整个矩阵从”直接距离”升级成”最短距离”，你甚至不需要额外的存储结构。这也是”矩阵 + 算法”配合最默契的经典案例。

第三个是可达矩阵：格子只回答”从 i 能不能走到 j”，能填 1，不能填 0。它相当于把”路径可达性”预计算好存起来，之后所有”u 能不能到 v”的查询都是 O(1)。代价是预计算本身要花时间（通常 Floyd 一趟 O(V³)），而且矩阵的空间依旧是 O(V²)。当一张图”只查不改”、查询量又特别大时，可达矩阵是典型的”用预处理换查询速度”。

另外提一个压缩技巧：如果矩阵只存 0/1，理论上可以把每个格子压成 1 个比特位，整张矩阵从 V² 字节变成 V²/8 字节，省 8 倍内存；很多语言提供位集（bitset）工具，配合位运算还能加速某些矩阵操作。不过压缩会牺牲”直接按下标读取”的便利性，工程里是否值得，取决于内存是不是瓶颈。

记住这三个变体，你就明白为什么面试官总爱问”邻接矩阵还有什么用法”——因为同一个方阵，装布尔、装距离、装可达性，对应三种完全不同的算法场景。

小结一下邻接矩阵：它简单、直观、查边 O(1)，是”用空间换时间”的典型代表；代价是空间恒为 O(V²)，遍历邻居也要花 O(V)。它适合顶点少、图稠密、或者算法高频查边的场景。要是图又大又稀疏，我们就要请出下一位主角——邻接表。

第 3 章 邻接表：每个顶点一张”朋友名单”

3.1 定义：我的邻居，我单独记一份

邻接表的思路，一句话就能讲清：给每个顶点准备一张小名单，名单上只写它自己直接相连的邻居。谁是我的朋友，我这张名单上就写谁；跟我没关系的人，我这张名单上一个字都不提。

具体到数据结构上，邻接表通常是一个长度为 V 的数组（或对象），数组的第 u 个位置挂着顶点 u 的”名单”。名单本身可以是数组、链表、或者任何支持增删查的容器。如果是无权图，名单里只需要存邻居的编号；如果是带权图，每个条目还要附上这条边的权重，通常存成一个二元组 [邻居编号, 权重]。

这里有个关键细节：无向图的边不分方向，u—v 这条边要在两份名单里各出现一次——顶点 u 的名单里记上 v，顶点 v 的名单里记上 u。也就是说，无向图用邻接表存储时，7 条边实际会变成 14 个条目，每个条目代表”从某个顶点出发，能一步走到哪个邻居”。有向图则清爽得多：u→v 这条边只在 u 的名单里出现一次，因为从 v 出发并不能沿这条边走到 u。

为什么要存两份？因为”遍历 u 的邻居”这个操作，依赖的是”从 u 出发能到谁”的信息。对于无向图，u 能到 v，v 也能到 u，所以双方名单都得记。你可以把邻接表想象成电话簿：无向图里，我和你是互留电话的，你电话簿里有我，我电话簿里也有你；有向图里，我单向关注了你，只有我这边记着你，你那边没有我。

3.2 配图：例图 A 的邻接表长什么样

还记得第 1.3 节那张 6 顶点 7 条边的图吗？我们把它再画一遍，这次顺便把邻接表”摊”在它旁边：

flowchart LR
    0 ---|4| 1
    0 ---|2| 2
    1 ---|3| 2
    1 ---|5| 3
    2 ---|6| 4
    3 ---|1| 5
    4 ---|8| 5

逐个顶点写出它的邻居名单（带权），会得到下面这张”名单总表”：

顶点	邻居名单（含权重）	度数
0	1(4), 2(2)	2
1	0(4), 2(3), 3(5)	3
2	0(2), 1(3), 4(6)	3
3	1(5), 5(1)	2
4	2(6), 5(8)	2
5	3(1), 4(8)	2

你发现了吗：表格里每个顶点一行的长度，恰好等于它的度。顶点 3 只连了两条边，它的名单就只有两个条目；顶点 1 连了三条边，名单就有三个条目。邻接表的空间花费完全跟着”实际存在的边”走，边多则名单长，边少则名单短，绝不铺张浪费。

如果把”名单”画成更接近数据结构的样子——每个顶点是一个表头，后面挂着一串节点——长这样：

flowchart LR
    H0[表头 0] --> N01["邻居 1（边权 4）"]
    N01 --> N02["邻居 2（边权 2）"]
    H1[表头 1] --> N10["邻居 0（边权 4）"]
    N10 --> N12["邻居 2（边权 3）"]
    N12 --> N13["邻居 3（边权 5）"]
    H2[表头 2] --> N20["邻居 0（边权 2）"]
    N20 --> N21["邻居 1（边权 3）"]
    N21 --> N24["邻居 4（边权 6）"]
    H3[表头 3] --> N31["邻居 1（边权 5）"]
    N31 --> N35["邻居 5（边权 1）"]
    H4[表头 4] --> N42["邻居 2（边权 6）"]
    N42 --> N45["邻居 5（边权 8）"]
    H5[表头 5] --> N53["邻居 3（边权 1）"]
    N53 --> N54["邻居 4（边权 8）"]

这种”表头 + 一串节点”的样子，就是教科书里经典的链式邻接表。不过请记住：链表只是邻接表的一种实现载体。在实际代码里，用数组套数组往往更常用，因为数组在内存里连续存放，访问快、写起来短；而链表的好处是中间插入删除灵活，概念上也更贴近”每个人手里一张名单”。两种实现我们都会在后面给出代码。

3.3 空间 O(V + E)：与图的实际大小成正比

邻接表的空间复杂度是 O(V + E)。拆开看：V 个表头，每个表头 O(1) 空间，一共 O(V)；每条无向边在两张名单里各出现一次，贡献 2 个条目，一共 O(E)（有向图每条边只出现一次，也是 O(E)）。合起来，空间就是”顶点数 + 边数”的线性规模。

用第 1.3 节的例子算一笔账：6 个顶点、7 条边，邻接表需要 6 个表头加 14 个边条目；而同样这张图，邻接矩阵需要 6×6 = 36 个格子，其中只有 14 个格子有边（不含对角线），超过六成的格子是浪费的 ∞。如果图再大一点、再稀疏一点，这个差距会拉得更悬殊：1 万个顶点、2 万条边的稀疏图，邻接表大约只需 3 万个存储单元；邻接矩阵却要 1 亿个格子——差了三千多倍。

所以邻接表是稀疏图的”天然主场”。现实世界里的绝大多数图都是稀疏图：社交网络每人平均只有几百个好友，地图路口平均只有四五个方向，网页平均只有几十个超链接。相比顶点总数，每个顶点的邻居数小得可怜。这也是为什么工程上邻接表（及其变体）是默认选择，邻接矩阵反而是特例。

3.4 三种操作在邻接表上的账本

还是那三本账，这次算给邻接表：

遍历邻居 neighbors(u)：直接取出顶点 u 的名单，从头到尾走一遍，O(deg(u))。deg(u) 是 u 的度。对稀疏图来说 deg(u) 通常很小（平均个位数到几百），所以这个操作快得惊人。DFS、BFS 这类算法每次扩展一个顶点都只花 O(deg(u))，整个遍历过程加起来是 O(V + E)，这是邻接表最闪亮的优势；

查边 hasEdge(u, v)：需要到 u 的名单里线性寻找 v，O(deg(u))。如果名单用数组存且不排序，最坏情况要看到最后一个条目；如果名单用哈希集合（如 Set）实现，可以做到 O(1) 平均。不过哈希集合不方便同时携带多个邻居信息（权重、多条平行边），所以大多数加权图实现还是用数组，接受 O(deg) 的查边代价；

遍历所有边 allEdges()：把 V 个表头都访问一遍，再访问每条边的条目，O(V + E)。注意无向图每条边会出现两次，所以代码里要小心别把同一条边统计两遍；通常可以用”只处理编号小的端点指向编号大的端点的条目”来去重。

度数的统计也顺便说清：无向图里，顶点 u 的度就是它名单的长度，O(1) 就能拿到；有向图里，u 的出度是名单长度，O(1)；但 u 的入度可没那么容易——你得遍历所有顶点的名单，数一数有多少个条目写着 u，O(V + E)。这个”入度难求”的问题，我们在第 7 章介绍逆邻接表时会专门解决。

3.5 代码实现：数组套数组与链式两种写法

先看最常用的实现——外层一个数组，内层每个顶点一个数组。加权无向图可以这样写：

// 带权无向图的邻接表实现（数组套数组）
class WeightedUndirectedGraphList {
  // adj[u] 是顶点 u 的邻居列表，每个条目是 [邻居编号, 权重]
  private adj: Array<Array<[number, number]>>;

  constructor(vertexCount: number) {
    this.adj = Array.from({ length: vertexCount }, () => []);
  }

  // 无向边：u 的名单加 v，v 的名单加 u
  addEdge(u: number, v: number, w: number): void {
    this.adj[u].push([v, w]);
    this.adj[v].push([u, w]);
  }

  // 查边：在 u 的名单里找 v
  hasEdge(u: number, v: number): boolean {
    return this.adj[u].some(([to]) => to === v);
  }

  // 取邻居：直接返回整张名单（引用），遍历时无需复制
  getNeighbors(u: number): Array<[number, number]> {
    return this.adj[u];
  }

  // 无向图的度 = 名单长度
  degree(u: number): number {
    return this.adj[u].length;
  }

  // 遍历所有边（无向图去重：只取 from < to 的条目）
  *allEdges(): Generator<[number, number, number]> {
    for (let u = 0; u < this.adj.length; u++) {
      for (const [v, w] of this.adj[u]) {
        if (u < v) yield [u, v, w];
      }
    }
  }
}

如果你只想要无权图，把条目从 [邻居, 权重] 换成单纯的邻居编号 number，代码会更短：addEdge 里 push(v) 和 push(u) 两行，hasEdge 用 includes，getNeighbors 返回 number[]。很多在线判题平台的模板就是这种”vector 套 vector”（C++ 里是 vector<vector>，Java 里是 List<List>），概念完全一致。

再看链式实现。它更贴近”表头挂链表”的教科书形象：每个表头指向一个节点，节点里存着邻居编号、权重和指向下一个节点的指针。在 TypeScript 里可以这样写：

// 链式邻接表：一个边节点
interface EdgeNode {
  to: number;          // 邻居顶点
  weight: number;      // 边权
  next: EdgeNode | null; // 指向下一个邻居节点
}

class LinkedGraph {
  private heads: Array<EdgeNode | null>;

  constructor(vertexCount: number) {
    this.heads = Array(vertexCount).fill(null);
  }

  // 头插法：新邻居插到链表最前面，O(1)
  addEdge(u: number, v: number, w: number): void {
    this.heads[u] = { to: v, weight: w, next: this.heads[u] };
    this.heads[v] = { to: u, weight: w, next: this.heads[v] }; // 无向图双向挂
  }

  // 查边：沿着链表找
  hasEdge(u: number, v: number): boolean {
    let cur = this.heads[u];
    while (cur) {
      if (cur.to === v) return true;
      cur = cur.next;
    }
    return false;
  }

  // 遍历邻居：沿链表走一遍
  *getNeighbors(u: number): Generator<[number, number]> {
    let cur = this.heads[u];
    while (cur) {
      yield [cur.to, cur.weight];
      cur = cur.next;
    }
  }
}

你可能会问：工程里到底用数组套数组还是链表？我的建议很直白：绝大多数时候用数组套数组。原因有三。第一，JavaScript/TypeScript 的数组在内存里连续存放，遍历时缓存友好，速度通常比散落各处的链表节点快；第二，代码更短，边界情况更少；第三，我们后面要实现的 BFS、DFS、Dijkstra 都只需要”顺序遍历邻居”和”把邻居放进队列/堆”，数组完全够用。链式实现的价值主要在教学和某些特殊场景：比如边频繁在中间插入删除，或者你正在学习数据结构课程、想看清”指针”是怎么串起一张图的。两种实现的时间复杂度相同，选择标准是”哪个写起来顺手、读起来明白”。

3.6 邻接表适合哪些算法和场景

邻接表是图算法世界的”万金油”。凡是”从一个顶点向外扩散”的算法，它都是首选：深度优先搜索 DFS、广度优先搜索 BFS、拓扑排序（Kahn 算法需要遍历每个顶点的出边）、单源最短路径 Dijkstra（配合优先队列）、强连通分量 Tarjan、二分图判定、最大流的 Dinic 分层……它们共同的特点是：反复调用”遍历邻居”，而邻接表让每次调用只花 O(deg) 而不是 O(V)。

现实工程场景里，地图导航（路网图，顶点是路口、边是道路，每个路口度数个位数）、社交网络（用户是顶点、关注/好友关系是边，平均度数几百）、知识图谱、依赖关系图、推荐系统的用户-物品二部图，几乎全部用邻接表或其工业变体存储。后面第 6 章我们还会展开讲这些例子。

邻接表唯一的短板，就是”查任意两点之间是否有边”比较慢——这在顶点多而每个顶点度数小的时候尤其明显。如果你的算法经常要问”u 和 v 认识吗”，而图又不算太大，可以考虑用邻接矩阵；或者折中一下：主结构用邻接表，再额外维护一个哈希集合存所有边，查边 O(1)，遍历邻居依然 O(deg)。这种”组合拳”在实际系统里很常见，不过那是工程优化的话题，我们先记住三种基础方案再说。

第 4 章 边集数组：把边全部平铺开

4.1 定义：图不就是一堆边吗

讲完前两种方案，你可能已经发现一个规律：邻接矩阵和邻接表，都坚持”以顶点为中心”来组织数据——矩阵按”顶点两两配对”开格子，邻接表按”每个顶点配名单”挂列表。但换个角度想，图的定义里，边本来就是独立存在的实体：一条边就是一条边，它自带着”起点 u、终点 v、权重 w”三个信息。那我们为什么不干脆把所有的边装进一个数组里，一条边占一个元素呢？

这就是第三种方案——边集数组（Edge List，也叫边表）。它的结构朴素到了极点：一个数组，数组的每个元素是一条边。用 TypeScript 描述，就是 { u: number; v: number; w: number } 这样的对象排成一排。无向图里，(u, v, w) 表示 u 和 v 之间有一条权重为 w 的边，u、v 顺序无所谓；有向图里，(u, v, w) 表示从 u 指向 v、权重为 w 的有向边，u、v 顺序有严格意义。

你可能觉得这也太简单了，简单得不像个正经数据结构。但请记住：数据结构的好坏取决于用途，而不是造型的华丽。边集数组虽然”查边”和”找邻居”都慢，但它有一个别人比不了的绝活——把全部边一次性端出来，想怎么排序就怎么排序。就凭这个绝活，它在图论算法里占据着不可替代的位置。

4.2 配图：例图 A 的边集长什么样

还是那张老朋友图：6 个顶点、7 条带权无向边。

flowchart LR
    0 ---|4| 1
    0 ---|2| 2
    1 ---|3| 2
    1 ---|5| 3
    2 ---|6| 4
    3 ---|1| 5
    4 ---|8| 5

把它转成边集数组，就是下面这 7 条记录，每条记录三个字段：起点、终点、权重。数组里的顺序完全随意，先存哪条后存哪条都行，不影响图的含义：

flowchart LR
    E0["边 0：0 → 1，权重 4"]
    E1["边 1：0 → 2，权重 2"]
    E2["边 2：1 → 2，权重 3"]
    E3["边 3：1 → 3，权重 5"]
    E4["边 4：2 → 4，权重 6"]
    E5["边 5：3 → 5，权重 1"]
    E6["边 6：4 → 5，权重 8"]

在真实代码里，这 7 条记录就是数组里的 7 个对象；上面这张图只是把它们”摊开”给你看。注意每条边都只出现一次——无向图在边集里不需要存两遍，因为它不像邻接表那样要服务”从每个顶点找邻居”的查询，它只忠实记录”图中存在哪些边”这个事实。

4.3 空间 O(E)：最小巧的存法

边集数组的空间复杂度是 O(E)：E 条边，每条边固定存 u、v、w 三个字段（外加对象开销），没有别的结构性开销。它不需要为每个顶点预留位置，也不存在”每条边存两份”的浪费，是所有方案里最省空间的。

但这有个前提：你得另外想办法知道顶点集合长什么样。边集数组里如果出现一个顶点 9，你只能从某条边的 u 或 v 字段里”顺带发现”它；如果存在孤立顶点（一条边都不连），它压根不会出现在边集里。所以使用边集数组时，程序通常还会额外维护一个顶点集合，或者约定顶点编号是连续的 0 到 V-1，由外部传入 V。这也是它和邻接表的一个重要区别：邻接表的 V 个表头天然”代表”了顶点存在，边集数组则把顶点信息完全交给了边去”捎带”。

在文件格式和系统间交换的场合，边集数组几乎是标准答案：很多图的数据文件就是一行一条边，形如 0 1 4，读取时按行解析，存进边数组即可。社交网络研究里常用的数据集（如 SNAP 数据集）大多采用这种”边列表”格式，几亿条边也就是几个大文件，读起来飞快。

4.4 天生为 Kruskal 而生：为图系列第 12 篇埋个伏笔

边集数组最闪光的应用，是求最小生成树的 Kruskal 算法。我先不展开讲 Kruskal 的完整原理（那会在图系列第 12 篇详细登场），但可以让你先看一眼它为什么离不开边集数组。

最小生成树的问题是：给一张带权无向连通图，选出一部分边，把所有顶点连通起来，并且选出的边总权重最小。Kruskal 的思路非常朴素——把所有的边按权重从小到大排序，然后一条一条地看：如果这条边连接的两个顶点还不属于同一个”集团”，就把它选进生成树；如果它们已经连通了，就跳过，因为再加它就会形成环。这个过程一直持续到选够 V-1 条边为止。

你发现问题了吗？Kruskal 的第一步就是”把全部边按权重排序”，第二步是”按顺序逐条处理边”。这两个操作，邻接矩阵做起来要先花 O(V²) 把边”挖”出来，邻接表做起来要把每条边（无向图还是两份）收集起来再去重排序，只有边集数组是现成的——边就在那里，一个 sort 调用，全图最轻、最重的边一目了然。这就是”数据结构为算法服务”的完美例证：Kruskal 需要什么操作，边集数组就提供什么操作。

另外，Bellman-Ford 单源最短路径算法也偏爱边集数组：它每一轮都要把”每一条边”拿出来做松弛（尝试更新两个端点的最短距离），“逐条遍历所有边”正是边集数组的主场。你可以把边集数组想象成一个仓库货架，Kruskal 和 Bellman-Ford 是两位按单取货的工人——货架上的货物（边）摆放整齐、清单明确，取货自然高效。

下面这张流程图，预览一下 Kruskal 拿到边集数组之后的操作顺序：

flowchart TD
    A[边集数组：7 条边] --> B[按权重从小到大排序]
    B --> C[取当前最小边 3→5 权重 1]
    C --> D{两个端点是否已连通}
    D -- 未连通 --> E[选入生成树，合并两个集团]
    D -- 已连通 --> F[跳过，防止形成环]
    E --> G{是否已选出 V-1 条边}
    F --> G
    G -- 未选够 --> C
    G -- 已选够 --> H[得到最小生成树]

看到没有，整条流水线的原料就是”一份边数组 + 一次排序”。等第 12 篇我们真正实现 Kruskal 时，你会觉得这段代码格外亲切。

4.5 三种操作在边集数组上的账本

算账时间到。边集数组在三种操作上的表现，和邻接矩阵几乎是对着来的：

遍历所有边 allEdges()：直接遍历数组，O(E)。这是它最强的一项，没有任何中间层，也没有重复条目；

查边 hasEdge(u, v)：从数组头扫到尾，逐条比较端点，O(E)。运气好第一条就命中，运气不好要看完所有边；

遍历邻居 neighbors(u)：同样得把整个数组扫一遍，凡是起点或终点含 u 的边都算邻居，O(E)。哪怕 u 只有 1 个邻居，也得翻遍全部 E 条边。

顺带算度数：无向图里顶点 u 的度 = 边数组中端点含 u 的边数，O(E) 扫一遍；有向图里 u 的出度 = 起点为 u 的边数，入度 = 终点为 u 的边数，都是 O(E)。

换句话说，边集数组把”遍历所有边”做到了极致，却把”局部查询”（查边、找邻居）变成了全表扫描。如果算法的主体操作是”反复从某个顶点向外探索邻居”，比如 BFS、DFS，用边集数组就是灾难——每次探索都要扫全表，总复杂度会从 O(V+E) 恶化到 O(E × V)。记住这个账本，你就永远不会拿边集数组去写 BFS。

4.6 代码实现：一个数组走天下

边集数组的代码是三种方案里最短的。先定义边的类型，再实现增边、查边、找邻居和按权重排序：

// 一条带权边：u 到 v，权重 w
interface Edge {
  u: number;
  v: number;
  w: number;
}

class EdgeListGraph {
  // 全部边平铺在一个数组里
  private edges: Edge[] = [];
  private vertexCount: number;

  constructor(vertexCount: number) {
    this.vertexCount = vertexCount;
  }

  // 加一条边（无向图）
  addEdge(u: number, v: number, w: number): void {
    this.edges.push({ u, v, w });
  }

  // 查边：线性扫描
  hasEdge(u: number, v: number): boolean {
    return this.edges.some(
      (e) => (e.u === u && e.v === v) || (e.u === v && e.v === u)
    );
  }

  // 找邻居：线性扫描，收集所有含 u 的边
  getNeighbors(u: number): Array<[number, number]> {
    const result: Array<[number, number]> = [];
    for (const e of this.edges) {
      if (e.u === u) result.push([e.v, e.w]);
      else if (e.v === u) result.push([e.u, e.w]);
    }
    return result;
  }

  // 按权重从小到大排序（Kruskal 的第一步）
  sortedByWeight(): Edge[] {
    return [...this.edges].sort((a, b) => a.w - b.w);
  }
}

// 使用示例：构造第 1.3 节的例图
const g = new EdgeListGraph(6);
g.addEdge(0, 1, 4);
g.addEdge(0, 2, 2);
g.addEdge(1, 2, 3);
g.addEdge(1, 3, 5);
g.addEdge(2, 4, 6);
g.addEdge(3, 5, 1);
g.addEdge(4, 5, 8);

console.log(g.hasEdge(1, 3)); // true
console.log(g.getNeighbors(2)); // [[0,2],[1,3],[4,6]]
console.log(g.sortedByWeight());
// 排序后第一条是 3→5 权重 1，最后一条是 4→5 权重 8

如果是有向图，把 hasEdge 和 getNeighbors 里”反过来也算”的分支去掉即可：hasEdge 只比较 e.u === u && e.v === v，getNeighbors 只收集 e.u === u 的边。代码几乎不用改结构。

小结边集数组：它空间最省、实现最简单、遍历所有边最快，但局部查询全要靠线性扫描。它是 Kruskal 和 Bellman-Ford 这类”面向全图边集合”算法的黄金搭档，也是图数据交换的标准格式。现在，三位主角都已经出场完毕，是时候把三张账本摆在一起，做一次正面对比了。

第 5 章 三张账本摆在一起：横向对比

5.1 一张表看穿三种方案

为了对比公平，我们统一用带权图来比较，并且假设 V 个顶点、E 条边。表格里的复杂度是”最坏情况”；无向图在邻接表中每条边存两份，这个 2 倍常数不影响 O 记号，我就在备注里提一句。

对比维度	邻接矩阵	邻接表	边集数组
空间复杂度	O(V²)	O(V + E)	O(E)
空间特点	与边数无关，边再少也铺满 V²	与图实际规模线性相关	最紧凑，但孤立点要靠外部记录
查边 hasEdge	O(1)，直接读格子	O(deg(u))，在名单里找	O(E)，全表扫描
遍历邻居	O(V)，扫一整行	O(deg(u))，直接走名单	O(E)，全表扫描
遍历所有边	O(V²)，扫全矩阵	O(V + E)，无向图要防重复	O(E)，直接走数组
顶点 u 的度	O(V)（数行/列）	无向图 O(1)，出度 O(1)，入度 O(V+E)	O(E)（扫描统计）
实现难度	最简单	简单	最简单
典型算法	Floyd、传递闭包、矩阵幂	DFS、BFS、Dijkstra、拓扑排序、Tarjan	Kruskal、Bellman-Ford
适合图类型	稠密图、小图	稀疏图、通用首选	以边为中心的处理流程
动态加边	O(1)	O(1)（数组尾插）	O(1)（数组尾插）
动态加顶点	要重建矩阵，代价高	O(1) 往数组 push 一个空名单	只需更新顶点数
最大短板	空间爆炸、遍历邻居慢	查边偏慢、入度统计麻烦	局部查询全靠全表扫描

这张表值得你花几分钟慢慢读。你会发现一个有趣的规律：三种方案的优缺点几乎是”零和”的——矩阵把查边做到 O(1)，代价是空间 O(V²) 和遍历邻居 O(V)；边集把遍历所有边做到 O(E)，代价是查边和找邻居都退化成 O(E)；邻接表站在中间，遍历邻居最快，其他两项都是”能接受但不出彩”。正因为如此，选择存储方式没有”标准答案”，只有”适不适合当前问题”。

5.2 别背表，背”操作决定存储”这句话

如果你觉得上面的表格信息量太大，我给你提炼成一句话：你的算法需要反复做哪种操作，就选哪种操作最快（或代价可接受）的存储方案。

拿遍历类算法举例。DFS 和 BFS 的骨架都是”从当前顶点出发，依次访问所有邻居”：在邻接表上，访问一个顶点的全部邻居只要 O(deg)，整个遍历 O(V + E)；在邻接矩阵上，访问一个顶点的全部邻居要扫一整行 O(V)，整个遍历 O(V²)；在边集数组上，每次找邻居都要扫全表 O(E)，整个遍历可能达到 O(V × E)，对稍大的图来说完全不可用。所以 DFS/BFS 几乎总搭配邻接表——这不是习惯问题，是复杂度逼出来的选择。

再看全源最短路径 Floyd-Warshall。它的核心转移是”看 A[i][k] 和 A[k][j] 的值，试着更新 A[i][j]“，也就是高频的”任意两点查边”。邻接矩阵把每次查询压到 O(1)，三重循环的总复杂度就是 O(V³)；如果用邻接表，每次”查边”都要在名单里线性找，最坏情况会多出 O(V) 的系数，变成 O(V⁴)，性能断崖式下跌。而 Kruskal 需要”把全部边按权重排序、逐条处理”，边集数组一步到位，矩阵要先花 O(V²) 收集边，邻接表要处理重复条目，平白多出许多无用功。

下面这张”算法 × 存储”的匹配图，把这个规律画成了对应关系，你可以把它当作选型速查卡：

flowchart LR
    DFS["DFS / BFS<br/>需要快速遍历邻居"] --> AL[邻接表]
    DIJ["Dijkstra<br/>需要快速遍历邻居"] --> AL
    TOPO["拓扑排序<br/>需要遍历出边"] --> AL
    FLOYD["Floyd-Warshall<br/>需要高频查任意两点"] --> AM[邻接矩阵]
    CLOSURE["传递闭包<br/>矩阵运算友好"] --> AM
    KRUSKAL["Kruskal<br/>需要按权重遍历全部边"] --> EL[边集数组]
    BELLMAN["Bellman-Ford<br/>需要反复松弛全部边"] --> EL

注意，这张图讲的是”首选”，不是”唯一”。你完全可以用邻接表实现 Floyd（顶点少的时候性能差异不明显），也可以用邻接矩阵实现 BFS（小图完全没问题），还可以给 Kruskal 喂邻接表（先把边收集出来再排序）。只是当图规模变大，选错存储的代价会成倍放大——这就是为什么在动手写算法前，先想清楚”用什么装这张图”。

5.3 复杂度之外的现实因素

表格里还有一个容易被忽略的维度：常数因子和内存布局。大 O 记号告诉我们”规模变大时谁更快”，但实际运行还受常数影响。邻接表里每个条目是一个对象/二元组，比矩阵里的裸数字多一层包装；现代 CPU 对连续内存的访问远快于跳来跳去的指针，所以同样 O(V+E) 的遍历，数组套数组的邻接表通常比链式邻接表快不少。这也是我在 3.5 节建议优先用数组的原因。

另一个现实因素是”图的演化方式”。如果图在运行中会频繁增加或删除顶点：邻接矩阵每次加顶点都要扩容到 (V+1)²，可能整体拷贝一次，代价很高；邻接表只需 push 一个新空数组，O(1) 摊还；边集数组更是无感。反过来，如果边数基本固定、图是”一次性读入”，边集数组这种扁平结构反而最友好。

还有一个容易被面试官抓住的点：无向图邻接表里每条边存两份，遍历所有边时容易重复计数。写代码时要约定去重规则，比如”只处理 u < v 的条目”。矩阵天然没有这个问题（每个格子唯一），边集数组也没有（每条边唯一）。这些细节看似琐碎，却是真实工程 bug 的高发地。

5.4 一个贯穿案例：同一趟 BFS，三种存储差多远

光看复杂度符号，你可能还感受不到差距有多悬殊。我们用”跑一趟广度优先搜索 BFS”来算一笔实账——下一篇我们就会正式实现它，现在只需要知道：BFS 的基本动作是”每个顶点出队一次，出队时把它所有的邻居挨个看一遍”。

在邻接表上，顶点 u 出队时遍历它的名单要花 O(deg(u))，所有顶点加起来，正好把每条边（无向图是每份条目）都看过一次，总时间 O(V + E)。在邻接矩阵上，顶点 u 出队时要把第 u 行整行扫一遍（因为只有扫完才知道哪些格子有边），无论它的真实度数有多小，都是 O(V)；V 个顶点全部出队，总时间 O(V²)。在边集数组上，顶点 u 出队时为了找邻居，得把 E 条边全部扫一遍，O(E)；V 个顶点全部出队，总时间 O(V × E)。

把三种方案的账并列摆出来：

存储方案	每个顶点出队的开销	整趟 BFS 总开销
邻接表	O(deg(u))	O(V + E)
邻接矩阵	O(V)	O(V²)
边集数组	O(E)	O(V × E)

代入一张真实规模的稀疏图：V = 10 万、E = 30 万。邻接表大约做 40 万次基本操作，毫秒级完成；邻接矩阵要做 10 的 10 次方次操作，慢上几个数量级；边集数组更夸张，要 10 的 10 次方乘 3 次操作，完全不可用。同样一张图、同一个算法，只是换了个”装法”，性能竟能差出几个数量级——这就是”存储决定算法成败”最生动的证据。

顺便说一个经常被问到的细节：为什么矩阵 BFS 是 O(V²) 而不是 O(V² + E)？因为矩阵本身就包含全部边信息，扫行的时候边已经”顺带”被看过了，不必再单独统计 E；而邻接表里边信息分散在名单里，遍历名单恰好就是遍历边，所以是 O(V + E)。理解这个区别，你对”复杂度到底在数什么操作”会有更深的感觉。

第 6 章 选择指南：拿到一张新图，我该怎么存

6.1 先问自己三个问题

学完三种方案，你最想要的肯定是一个”开箱即用”的决策方法：给我一张图，我一眼就能判断该用哪种存法。这里给你一套三步走的判断流程，每一步都是一个简单问题。

第一个问题：图有多大？更准确地说，V 和 E 的量级分别是多少。V 只有几十、几百，那随便哪种方案都行，优先选写着舒服的；V 上万甚至上亿，邻接矩阵基本出局，只能在邻接表和边集数组里挑。判断”上不上万”不需要精确数字，只要心里有数：V² 会不会把内存撑爆。

第二个问题：主要操作是什么？这个问题的答案直接决定方案，比第一个问题更重要。如果算法是 BFS、DFS、Dijkstra 这类”从顶点向外扩散”的，选邻接表；如果算法高频查询”任意两点之间有没有边”，比如 Floyd 和传递闭包，选邻接矩阵；如果算法要”把全部边排序、逐条处理”，比如 Kruskal 和 Bellman-Ford，选边集数组。

第三个问题：图会怎么变化？边是静态读入还是一直增删？顶点会不会新增？运行期频繁加顶点，矩阵的重建成本难以承受；图基本不变，边集数组的扁平结构最省事。这三个问题问完，答案往往已经呼之欲出。

6.2 稠密还是稀疏：用数字说话

“稠密""稀疏”这两个词在 1.3 节就出现过，现在是时候给出更精确的判据了。V 个顶点的无向简单图，边数上限是 V(V-1)/2；如果 E 的数量级接近这个上限（也就是 E = O(V²)），图是稠密的；如果 E 只有 O(V) 或者更小，图是稀疏的。

一个常用的量化指标叫”图的密度”，无向图定义成 d = 2E / (V(V-1))，取值在 0 到 1 之间。d 越接近 1，图越接近完全图；d 接近 0，图就越”空”。你不需要背公式，只要记住直觉：平均每个顶点的邻居数（平均度）如果很小，比如个位数到几十，而顶点数很大，那一定是稀疏图；平均度接近顶点数，才是稠密图。

把两种极端画出来，一眼就能看出差别：

flowchart LR
    subgraph Sparse[稀疏图：V 大、边少]
        direction LR
        s0((0)) --- s1((1))
        s0 --- s2((2))
        s1 --- s3((3))
        s2 --- s4((4))
        s5((5)) --- s6((6))
        s7((7))
    end
    subgraph Dense[稠密图：顶点少、边接近满配]
        direction LR
        d0((0)) --- d1((1))
        d0 --- d2((2))
        d0 --- d3((3))
        d1 --- d2
        d1 --- d3
        d2 --- d3
    end

左边是典型的稀疏图：顶点不少，但每个顶点只连寥寥几条边，画出来”漏风漏雨”；右边是典型的稠密图：4 个顶点连满 6 条边，密不透风。判断完稠密稀疏，再套用 6.1 的三个问题，选型就八九不离十了。

6.3 决策流程：一张流程图走到底

把上面的判断串成一张流程图，就是下面这样。你从入口开始，一路回答”是/否”，最后会落到某个推荐方案：

flowchart TD
    START[拿到一张图] --> Q1{顶点数 V 是否很小<br/>且需要高频查任意两点}
    Q1 -- 是 --> MATRIX[邻接矩阵<br/>如 Floyd、传递闭包]
    Q1 -- 否 --> Q2{主要操作是<br/>从顶点向外遍历邻居}
    Q2 -- 是 --> LIST[邻接表<br/>如 BFS、DFS、Dijkstra]
    Q2 -- 否 --> Q3{主要操作是<br/>按权重处理全部边}
    Q3 -- 是 --> EDGES[边集数组<br/>如 Kruskal、Bellman-Ford]
    Q3 -- 否 --> DEFAULT[默认邻接表<br/>通用性最好，代价均衡]

注意流程图里的”默认”分支：当你既不确定操作、图又比较大时，邻接表是最稳的选择。它是唯一在”遍历邻居”上最优、在”空间”上线性、在”查边”上尚可接受的方案，综合平衡性最好。反过来，如果你明确知道”这道题就是 Floyd”，那就别犹豫，直接矩阵——哪怕图是稀疏的，只要 V 足够小（几千以内），矩阵的内存和速度都是最优解。

6.4 两个真实世界的例子：地图与社交网络

让我们用两个最常被提起的真实场景，把选型流程走一遍。

第一个场景是地图导航。一张城市路网图，路口是顶点，道路是边。北京市区级别的路网大约有几十万个路口，每条道路带长度或通行时间权重。V 是几十万，平均每个路口的度数是个位数（十字路口连 4 条路，五岔路口连 5 条），E 大约是 V 的好几倍——毫无疑问的稀疏图。导航软件要做的核心操作是 Dijkstra 或 A* 最短路径，它们每轮都要从当前路口向外遍历邻居。于是答案非常清楚：邻接表，而且是数组套数组的加权邻接表，配合优先队列。如果换成邻接矩阵，几十万顶点的方阵需要上万亿个格子，内存直接爆炸；如果换成边集数组，每次扩展邻居都要扫全表，导航一次要几十分钟，谁也等不起。

第二个场景是社交网络。微信有超过十亿用户，好友关系构成无向图（或微博式的关注关系构成有向图）。V 是十亿级别，平均每个用户的度数是几百，E 则达到千亿级别。这么大的图，单机内存根本装不下，工程上会拆到分布式系统里，按顶点分片存储”每个顶点的邻居列表”——本质上就是分布式的邻接表。同时，像”谁关注了我”这类入度查询，会再维护一份逆邻接表（每个顶点存”指向我的顶点列表”），这就是第 7 章的主角。在这个量级，邻接矩阵连讨论的资格都没有——十亿顶点平方后是一个天文数字，超出任何存储设备几个数量级。

那邻接矩阵在现实里就完全没用了吗？也不是。举几个常见例子：竞赛题里 V ≤ 500 的稠密图用矩阵跑 Floyd，几毫秒出结果；小规模的航班网络（几十个城市，两两之间可能有直飞航线）用矩阵存票价，查询”北京到上海直飞多少钱”就是一次 O(1) 数组访问；图论研究中计算图的幂、谱、特征值时，矩阵更是唯一自然的表示。你可以这么记：矩阵适合”小而全”的图，邻接表适合”大而疏”的图，边集适合”边单独派活”的图。

6.5 工程里的组合拳与进阶方案

真实系统很少只用一种存储。最常见的组合是”邻接表为主 + 哈希边集为辅”：主体用邻接表保证遍历邻居 O(deg)，再额外用一个 Set 存所有边（编码成 “u,v” 字符串或 u * V + v 数字），让查边也变成 O(1) 平均。代价是多一份边集合的副本，换来”两头快”，在很多需要同时做遍历和判重的算法里非常实用。

在大规模图计算的工业系统里，还有更讲究的存储，比如压缩稀疏行（CSR）：它用三个数组把邻接表压得几乎只剩数据本身，配合连续内存访问，性能极高，是图数据库和矩阵库处理稀疏图的标准格式。CSR 本质上还是邻接表的”压缩形态”，理解了邻接表，你就能轻松理解它。这一篇我们不展开，但你要知道：三种基础方案是地基，工业界的所有花活都是在地基上做优化。

最后给一句选型口诀，方便你随身携带：小图稠密用矩阵，大图稀疏用邻接表，边要排序用边集。 遇到拿不准的，默认邻接表，然后用 6.1 的三个问题重新过一遍，答案自然浮现。

6.6 三个练手场景：把口诀用起来

光背口诀不算会，我们来练三个具体场景，你可以在心里先给答案，再往下对。

场景一：十个城市之间的直飞航班表，要求随时回答”某两个城市之间有没有直飞、票价多少”，偶尔还要跑一次全源最短路径。你的选择？——邻接矩阵。顶点只有 10 个，矩阵只有 100 个格子，小得不能再小；而”查任意两点”是最高频操作，矩阵的 O(1) 直接命中需求，Floyd 也顺手。这种”小而全”的图，矩阵是标准答案。

场景二：一座城市的路网，30 万个路口、约 60 万条带长度权重的道路，核心算法是 Dijkstra 最短路径导航。你的选择？——加权邻接表，配合优先队列。路口多、平均度数小，图很稀疏；Dijkstra 每次要从当前路口拿到所有相邻路口，邻接表让这个操作只花 O(deg)；矩阵需要 90 亿个格子，内存直接出局；边集数组每次扩展都要扫 60 万条边，导航一次会慢到无法接受。

场景三：给你一个 100 万条边的文本文件，每行一条边，要求求出最小生成树。你的选择？——边集数组。文件本身就是边列表格式，读一行 push 一条，一个数组装完；Kruskal 要对全部边按权重排序，边集数组一条 sort 搞定，连转换都省了。这时候非要用邻接表，反而要先把边”铺”进表里、再收集出来排序，平白多绕一圈。

三个场景对照着记，你会发现口诀里每个词都有对应的操作：查两点、遍历邻居、排序全部边。把”操作”两个字抓住，选型就永远不会错。

第 7 章 有向图与权重：三种存储里的”方向感”

7.1 有向图：方向在三种存储里怎么表达

到目前为止，我们的例子几乎都是无向图。但现实里有大量关系是单向的：课程要先修后修，微博是单向关注，资金是单向流转，任务依赖有先后。第 2 篇里我们学过，有向图的边是带箭头的：u→v 表示从 u 指向 v，它和 v→u 是两条完全不同的边。那么三种存储方案要怎么表达”方向”呢？

邻接矩阵最简单：A[u][v] 和 A[v][u] 是两个独立的格子，各记各的。u→v 有边，就把 A[u][v] 填成权重；v→u 有没有边，完全看 A[v][u] 自己。因此有向图的矩阵一般不对称，这也是判断一张图是否有向的”视觉线索”——对称的是无向，不对称的很可能是有向。

邻接表的规则是：每条有向边 u→v 只出现在”起点 u”的名单里。换句话说，每个顶点的名单存的是它的出边——“从我能一步到谁”。第 3.1 节里”单向关注”的比喻就在这里应验：我关注了你，只有我这份名单记着你，你的名单里没有我。因为只有一条边，无向图那份”双向挂载”的重复也就消失了，存储量直接减半。

边集数组里，方向体现在三元组的顺序上：记录 (u, v, w) 表示从 u 到 v 的边，起点在前、终点在后。写代码时注意，addEdge(1, 2, 5) 和 addEdge(2, 1, 5) 在有向图里是两条不同的边，会占据两个不同的数组元素。

为了讲清楚有向图，我们换一个小例子：四门课程的先修关系。数据结构（记为 A）是算法设计（B）和操作系统（C）的先修课；算法设计（B）和操作系统（C）又都是编译原理（D）的先修课。于是有向边是 A→B、A→C、B→D、C→D。画出来是这样：

flowchart LR
    A["数据结构 A"] --> B["算法设计 B"]
    A --> C["操作系统 C"]
    B --> D["编译原理 D"]
    C --> D

用邻接表存这张图，每个顶点的名单恰好就是”学完这门课之后能解锁的课”：

顶点	出边名单（邻接表）
A	B, C
B	D
C	D
D	（空）

你马上能读出 A 的出度是 2，D 的出度是 0。但要问”哪些课是编译原理的直接先修课”（D 的入度），邻接表就答不上来了——你得把 A、B、C 的名单全翻一遍，数一数谁写着 D。这就是有向图里”入边查询”的经典难题，我们 7.3 节专门解决它。

7.2 权重：数字藏在哪，决定你的访问方式

带权图（也叫加权图）在三种存储里的差别不大，但值得逐一确认，因为面试和笔试里经常出现”存储选对了、权重存错地方”的失误。

邻接矩阵里，权重就是格子里的值：A[u][v] = 5 表示 u→v 的边权重为 5，没有边的地方填 ∞，对角线填 0。这里有个易错点：无权图里”有边”用 1、“无边”用 0，而带权图里”无边”必须用 ∞ 而不能用 0——因为 0 可能是一条合法边（免费通行、零成本）。选 ∞ 时还要注意数值上限：如果用 Number.MAX_SAFE_INTEGER，加法运算时可能溢出；竞赛代码里常用 1e9 这种”足够大又不溢出”的常数。

邻接表里，权重是每个条目的一部分：无向图的条目是 [邻居, 权重]，有向图的出边条目同样是 [终点, 权重]。读取权重时顺着名单找到终点即可，代价 O(deg)。如果图是”无权但有重复边”的（多重图），邻接表还比矩阵更能表达：同一个邻居可以出现多个条目，每个条目对应一条不同的平行边；而矩阵一个格子只能记一个值，表达多重图要么合并权重、要么额外加计数器。

边集数组里，权重就是三元组的第三个字段，和 u、v 平起平坐。这也是”边集”最擅长处理权重的体现：要按权重排序，直接对着第三个字段 sort；要统计权重和，一趟循环加起来。Kruskal 之所以首选边集数组，权重字段”随手可取”正是关键原因之一。

还有一个所有方案都适用的提醒：权重可能是负数（比如经济模型里的亏损、游戏里的反向传送门）。负权本身不影响”存储”，三种方案都能存负数；但负权会影响算法选择——比如 Dijkstra 就不能用于负权图，Bellman-Ford 可以。那是后面篇章的内容，这一篇你只需要知道”存储层对负数一视同仁”即可。

7.3 逆邻接表：专治”找入边”

现在解决 7.1 留下的难题：怎么快速回答”谁指向我”。

思路其实非常朴素：邻接表帮每个顶点存”我从哪出发能到谁”，那我们再建一张一模一样的表，帮每个顶点存”谁从哪出发能到我”不就行了？前者叫邻接表（存出边），后者叫逆邻接表（存入边）。两张表结构完全相同，只是边全部反了一个方向：原图里有 u→v，邻接表在 u 名下记 v，逆邻接表在 v 名下记 u。

用课程依赖图对照着看，最清楚：

flowchart LR
    subgraph N[正邻接表：出边]
        direction LR
        NA["A：B, C"] --- NB["B：D"]
        NB --- NC["C：D"]
        NC --- ND["D：（空）"]
    end
    subgraph R[逆邻接表：入边]
        direction LR
        RA["A：（空）"] --- RB["B：A"]
        RB --- RC["C：A"]
        RC --- RD["D：B, C"]
    end

对照着读：正邻接表里 B 名下写着 D，因为 B→D；逆邻接表里 D 名下写着 B 和 C，因为 B→D、C→D。这样，“编译原理的直接先修课有哪些”就变成了查 D 的名单：B、C，O(1) 时间拿到整个列表，再也不用全图扫描。

逆邻接表不是锦上添花，很多算法没有它根本跑不起来。最典型的是拓扑排序的 Kahn 算法：它先统计每个顶点的入度，把入度为 0 的顶点放进队列，每处理完一个顶点就把它的出边”删除”、更新受影响顶点的入度。维护入度表的前提，就是能 O(1) 拿到”我指向谁”（正邻接表）并且方便地更新”谁被影响”——其实还需要能 O(1) 拿到”谁的入度减少了”（出边终点列表）。再看依赖分析工具（比如构建系统），要回答”哪些包依赖这个包”（谁指向我），也必须有一份逆邻接表。数据科学里计算 PageRank 时，常需要按”入边聚合”处理，同样绕不开它。

构造逆邻接表非常简单：遍历原图所有边，把每条 u→v 反着写入逆表。空间额外 O(V + E)（对无向图来说逆表和正表内容相同，因为每条无向边双向都有，根本不需要另建）。代码也就十几行：

// 从正邻接表（出边）构造逆邻接表（入边）
function buildReverseGraph(
  outEdges: Array<Array<[number, number]>>
): Array<Array<[number, number]>> {
  const n = outEdges.length;
  const reverse: Array<Array<[number, number]>> = Array.from(
    { length: n },
    () => []
  );

  // 对每条出边 u → v，在逆表里记入边 v ← u
  for (let u = 0; u < n; u++) {
    for (const [v, w] of outEdges[u]) {
      reverse[v].push([u, w]);
    }
  }
  return reverse;
}

// 使用示例：课程依赖图 A→B, A→C, B→D, C→D
const out: Array<Array<[number, number]>> = [
  [[1, 1], [2, 1]], // A(0) 指向 B(1)、C(2)
  [[3, 1]],         // B(1) 指向 D(3)
  [[3, 1]],         // C(2) 指向 D(3)
  [],               // D(3) 无出边
];
const reverse = buildReverseGraph(out);
console.log(reverse[3]); // [[1,1],[2,1]]：B、C 都指向 D

在真实系统里，“正向表 + 反向表”常常成对出现：正表服务”我从哪出发”，逆表服务”谁来到我这”，两表结构相同、互为镜像。付出的代价是双份空间，换来的是两类查询都变快——这和第 6.5 节”邻接表 + 哈希边集”的组合拳是同一个思想：用空间换查询速度。

7.4 边界情况：多重图、自环与孤立点

前面我们一直默认图是”简单图”：任意两点之间最多一条边，且没有自环。但现实数据不总是这么守规矩，三种存储对边界情况的容纳能力也不一样，值得单独拎出来讲一讲。

先看多重图（两点之间有多条平行边）。邻接矩阵一个格子只能记一个数，表达”u 和 v 之间有两条权重不同的边”就很尴尬：要么只存其中一条（丢信息），要么存权重之和（丢结构），要么额外加一个计数（增加复杂度）。邻接表则天然胜任：u 的名单里可以出现两个指向 v 的条目，每个条目对应一条独立的平行边，权重各自记录，互不干扰。边集数组同样没问题：两条记录 (u, v, 3) 和 (u, v, 5) 并排躺着，谁也不会覆盖谁。所以如果数据里有大量平行边（比如运输网络里同一对城市有多条路线），邻接表和边集数组是更好的选择。

再看自环（从 u 出发回到 u 的边）。邻接矩阵里，自环就写在主对角线上：A[u][u] = 1 或对应权重。但要小心：我们约定对角线默认填 0 表示”原地不动代价为 0”，一旦出现自环，这个约定就被打破了，写算法时要额外注意区分”没有自环”和”自环权重为 0”。邻接表里，自环就是 u 的名单里出现一个指向自己的条目，处理起来毫无歧义；边集数组里则是一条 (u, u, w) 的记录，同样清晰。很多图算法（如最短路径、最小生成树）会显式忽略自环，因为自环对它们没有意义，但存储层面三种方案都能如实记录。

最后看孤立点（一条边都不连的顶点）。邻接矩阵里，孤立点对应一行一列全是 ∞，天然”存在”；邻接表里，孤立点有一个空的名单，也天然”存在”；但边集数组里，孤立点不会出现在任何一条边里——你从边集反推顶点集合，会漏掉它。这就是 4.3 节提醒过的：使用边集数组时，必须额外维护顶点集合或外部传入 V。当你从文件读入一张边列表时，最常见的 bug 就是”某个顶点只在边里出现过、或者根本没出现过”，处理时要格外小心。

还有一个和边界情况相关的细节：输入数据里的顶点编号可能不连续。比如真实数据集的顶点编号是 100、200、300……如果直接拿编号当下标，数组会浪费大量空间。工程上的标准做法是”重编号”：把所有出现过的顶点映射到连续的 0、1、2……，用一张哈希表记录原编号到新编号的对应关系。这一步在几乎所有真实图数据集的处理流程里都会出现，属于存储层”预处理”的基本功。

到这里，三种存储方案本身已经全部讲完，方向、权重这两个维度也补齐了。最后我们做一次全书收尾：一张速查表、几道自测题，再预告下一篇的精彩内容。

第 8 章 三种存储之间的转换

8.1 三种转换函数：想换就换

实际工程里，三种存储很少”老死不相往来”。最常见的流程是：数据文件是边列表（边集数组），算法要的是邻接表，中间必须做一次转换；或者题目给了邻接矩阵，你要把它变成邻接表才好写 BFS。学会转换，等于把三种方案打通了，手里的一张图可以随时换成最顺手的形态。

转换的原理都很直白，核心就是”遍历一种结构，往另一种结构里填”。我先给出三个最常用的转换函数，然后逐一解释。

// 转换 1：边集数组 → 无向图邻接表
function edgeListToAdjacencyList(
  vertexCount: number,
  edges: Edge[]
): Array<Array<[number, number]>> {
  const adj = Array.from({ length: vertexCount }, () => [] as [number, number][]);
  for (const { u, v, w } of edges) {
    adj[u].push([v, w]);
    adj[v].push([u, w]); // 无向图双向登记
  }
  return adj;
}

// 转换 2：无向图邻接表 → 边集数组（利用 u < v 去重）
function adjacencyListToEdgeList(
  adj: Array<Array<[number, number]>>
): Edge[] {
  const edges: Edge[] = [];
  for (let u = 0; u < adj.length; u++) {
    for (const [v, w] of adj[u]) {
      // 只保留"起点编号小于终点编号"的条目，天然去重
      if (u < v) edges.push({ u, v, w });
    }
  }
  return edges;
}

// 转换 3：无向图邻接矩阵 → 无向图邻接表
function matrixToAdjacencyList(
  matrix: number[][]
): Array<Array<[number, number]>> {
  const n = matrix.length;
  const adj = Array.from({ length: n }, () => [] as [number, number][]);
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      // 跳过对角线、跳过无边；只取上三角避免重复
      if (i < j && matrix[i][j] !== Infinity) {
        adj[i].push([j, matrix[i][j]]);
        adj[j].push([i, matrix[i][j]]);
      }
    }
  }
  return adj;
}

三个转换的时间复杂度分别是 O(E)、O(V+E)、O(V²)，都与”读一遍源结构”同阶，不会引入额外负担。要注意的细节只有两个：第一，无向图无论从哪个方向转，都要处理”每条边两个副本”的问题——边集转邻接表时是”一条边登记两处”，邻接表转边集时是”两份条目只导出一条边”，矩阵转邻接表时是”只扫上三角”；第二，带权图转换时要原样搬运权重，无权图转换时权重统一填 1 即可。

反过来，邻接表转邻接矩阵也经常用到，尤其当算法需要在”遍历”和”查边”之间切换时：先花 O(V+E) 把邻接表填进一个初始化为 ∞ 的矩阵，之后所有查边都变成 O(1)。代码就是把上面 matrixToAdjacencyList 的循环方向反过来，这里就不再重复了，留给你作为动手练习——自己写一遍，胜过看我写十遍。

掌握转换还有一个实际好处：读题时不用纠结”题目给的输入格式”和”我要用的算法”是否匹配。输入是边列表？没关系，一行转换函数喂给 BFS 用。输入是矩阵？没关系，转换成邻接表再跑 Dijkstra。存储是手段，算法才是目的——这句话，是本章最想让你带走的心法。

8.2 从文件读图的标准模板

真实世界的图很少在代码里手工一条条 addEdge，绝大多数来自文件：一行一个顶点、一行一条边。把”读文件 → 建图”这套流程固定成模板，能省掉你每次重复踩坑的时间。

常见的文本格式长这样：第一行是两个数字，表示顶点数 V 和边数 E；接下来 E 行，每行三个数字表示一条带权边 u v w。用 Node.js 读这种文件并建成邻接表，标准写法如下：

import { readFileSync } from "node:fs";

// 从文件读取无向带权图，返回 [顶点数, 邻接表]
function readGraphFromFile(path: string): [number, Array<Array<[number, number]>>] {
  const lines = readFileSync(path, "utf-8")
    .split(/\r?\n/)
    .map((line) => line.trim())
    .filter((line) => line.length > 0 && !line.startsWith("#")); // 跳过空行和注释

  const [V, E] = lines[0].split(/\s+/).map(Number);
  const adj = Array.from({ length: V }, () => [] as [number, number][]);

  for (let i = 1; i <= E; i++) {
    const [u, v, w] = lines[i].split(/\s+/).map(Number);
    adj[u].push([v, w]);
    adj[v].push([u, w]);
  }
  return [V, adj];
}

模板虽短，却藏着四个常见坑，值得一一说明。第一，行尾可能有 \r（Windows 换行），所以切行用 /\r?\n/ 而不是只认 \n；第二，文件里可能有空行或 # 注释行，读取时要过滤；第三，顶点编号不一定从 0 开始，如果编号是 1 到 V，要么给数组多开一位、让下标和编号对齐，要么先统一减一；第四，边数 E 必须和实际行数对上，读完后检查 i 是否恰好走到 E + 1，防止文件被截断。这四个坑每一个都在真实项目里出现过，写成模板后一次搞定。

如果你要建的是矩阵而不是邻接表，把目标结构换成二维数组、把 push 换成赋值即可，其余逻辑一字不改。掌握了这个模板，以后拿到任何”边列表文件”，你都能在三分钟内把它变成能跑的图——这是图算法实战的第一项基本功。

第 9 章 三种存储速查表

先把全篇最重要的结论浓缩成一张速查表。你可以把它截图存下来，以后写图相关的题或代码前先扫一眼，三秒钟完成选型：

方案	一句话记忆	空间	查边	遍历邻居	遍历所有边	首选算法	首选场景
邻接矩阵	所有配对各占一格	O(V²)	O(1)	O(V)	O(V²)	Floyd、传递闭包	小图、稠密图、高频查边
邻接表	每人一张朋友名单	O(V+E)	O(deg)	O(deg)	O(V+E)	DFS、BFS、Dijkstra、拓扑排序	大而稀疏的图、通用默认
边集数组	所有边平铺一排	O(E)	O(E)	O(E)	O(E)	Kruskal、Bellman-Ford	按权重排序、逐条处理全部边

对应到本文出现过的所有复杂度结论，再提醒三个容易踩的坑：

第一，无向图的邻接表每条边存两份，遍历全部边时记得去重（比如只处理起点编号小于终点编号的条目）；第二，带权图的矩阵”无边”要填 ∞ 而不是 0，否则会制造一堆”免费边”；第三，有向图的邻接表只存出边，需要频繁查入度/入边时，务必补一张逆邻接表。

术语也一并汇总一下，方便你日后回顾：

术语	一句话解释
稀疏图 / 稠密图	边数接近 O(V) 的是稀疏图；接近 O(V²) 的是稠密图
平均度	所有顶点度数之和除以顶点数，用于判断稀疏程度
图的密度	d = 2E / (V(V-1))，越接近 1 越稠密
邻接矩阵	V×V 二维数组，A[i][j] 记录 i 到 j 的边/权重
邻接表	每个顶点一条列表，记录它的邻居（和权重）
边集数组	一个数组存所有边，每条边是 (u, v, w) 三元组
出边 / 入边	有向图中从某顶点出发的边 / 指向某顶点的边
逆邻接表	每个顶点记录”谁指向我”，与邻接表互为镜像
CSR	压缩稀疏行，邻接表的高压缩工业形态

再附一张”内存估算小抄”，帮你把抽象的 O 记号翻译成具体的字节数。假设权重用 4 字节整数存储，并忽略对象包装和数组自身的固定开销：

图的规模	邻接矩阵	邻接表	边集数组
V=1000，E=2000	100 万格 ≈ 4 MB，浪费约 98%	表头 4 KB + 条目 16 KB，共约 20 KB	约 24 KB
V=10000，E=30000	1 亿格 ≈ 400 MB，直接出局	约 300 KB	约 360 KB
V=100000，E=300000	100 亿格 ≈ 40 GB，不可行	约 3 MB	约 3.6 MB

注意同一行里三个数字的差距：顶点到一万级时，矩阵已经是邻接表的一千多倍；到十万级时，矩阵大到无法放进单机内存，而邻接表只要几兆。这张小抄配合第 6 章的决策流程，足够应付绝大多数选型问题了。还要记住，真实语言里对象有额外开销（比如一个边对象通常占 30~50 字节），邻接表和边集的真实内存会比理想数字高 2 到 4 倍，但量级关系不变——矩阵的 V² 照样碾压一切。

自测题：检验你的存储功力

下一篇预告：广度优先搜索 BFS

存储问题解决后，我们终于可以放开手脚在图上”走路”了。下一篇《图系列第 4 篇：广度优先搜索 BFS》，我们将第一次真正把图”走”起来：从一个起点出发，先访问它的所有邻居，再访问邻居的邻居，像水面上的涟漪一样一圈一圈向外扩散。

你会看到，BFS 是建立在邻接表之上最优雅的算法之一：一个队列、一个已访问标记、一个”层”的概念，就能解决一堆看似复杂的问题——无权图的最短路径（最少经过几条边）、判断两个顶点是否连通、求社交网络里”你与陌生人之间隔着几个人”、在迷宫里找最短出口，甚至把图”分层”用于后续的二分图判定和最大流算法。我们会亲手用 TypeScript 实现它，并用第 1.3 节那张 6 顶点 7 条边的老朋友图，一步一步模拟队列的变化过程。

先给你画一张 BFS 的”涟漪图”预热一下。假设从顶点 0 出发，第一圈访问 0 的邻居（第 1 层），第二圈访问它们的邻居（第 2 层），依次类推：

flowchart LR
    S[起点 0] --> L1A[第 1 层：顶点 1]
    S --> L1B[第 1 层：顶点 2]
    L1A --> L2A[第 2 层：顶点 3]
    L1B --> L2B[第 2 层：顶点 4]
    L2A --> L3A[第 3 层：顶点 5]
    L2B --> L3A

下一篇的核心问题只有一个：怎么保证”先访问近的，再访问远的”？答案就藏在”队列”两个字里。我们下一篇见。