12 - 图怎么存、怎么走

上一章认识了图。这一章解决两个最基础的问题：图在计算机里怎么存下来？怎么把它一个不漏地走一遍？ 这是所有图算法的地基。

第一件事：图怎么存

图是「点 + 连线」，计算机里没有「线」这种东西，得想办法记录「谁和谁相连」。有两种主流存法。

存法一：邻接矩阵（用一张大表）

用一个 N×N 的表格，行和列都是所有顶点。第 i 行第 j 列填 1 表示「i 和 j 相连」，填 0 表示不连。

       A  B  C  D
    A [ 0  1  1  0 ]
    B [ 1  0  0  1 ]
    C [ 1  0  0  1 ]
    D [ 0  1  1  0 ]

• 优点：查「A 和 B 到底连没连」超快，直接看表格对应格子，O(1)。
• 缺点：费空间。不管实际有多少条边，都得占 N×N 的格子。如果顶点很多、边却很少（比如社交网络里，你不可能认识所有人），这张表大部分是 0，浪费巨大。

适合「顶点不多、边很密」的图。

存法二：邻接表（每个点记个小名单）

给每个顶点配一个列表，只记录「我直接连着谁」。

A → [B, C]
B → [A, D]
C → [A, D]
D → [B, C]

• 优点：省空间，有多少条边就存多少，不浪费。
• 缺点：查「A 和 B 连没连」得翻一下 A 的名单，比矩阵稍慢。

适合「顶点多、边稀疏」的图——现实中的大多数图都是这种（社交、地图、网页），所以邻接表是更常用的存法。

一句话选择：

边密、点少用邻接矩阵（查得快）；边稀、点多用邻接表（省空间）。 大多数真实场景用邻接表。

第二件事：怎么把图走一遍（遍历）

存好了，现在要「不重不漏地访问每个顶点」。因为图有环、有交叉，走的时候必须记住哪些点已经访问过（否则会绕圈子无限循环）。有两种走法，它们的差别特别经典。

走法一：广度优先搜索（BFS）——一圈圈往外扩

从起点出发，先访问所有「直接邻居」，再访问「邻居的邻居」，像水波纹一样一圈圈向外扩散。

从 A 出发：
第 1 圈：A
第 2 圈：A 的邻居 → B, C
第 3 圈：B、C 的邻居 → D

• 怎么实现？用队列（第 05 章！）：访问一个点，就把它没访问过的邻居都排进队列尾部，然后从队头取下一个来访问。先发现的先处理，天然实现「由近及远」。
• 擅长：找最短路径（在不带权图里）。因为它是一圈圈扩的，第一次到达某个点时，走的一定是最少的步数。

  「你和某人之间隔几层关系」「迷宫最少几步走出去」——这类「最近/最少步数」问题用 BFS。

走法二：深度优先搜索（DFS）——一条路走到黑

从起点出发，沿着一条路使劲往下走，走到不能再走（死胡同）为止，再退回来换一条没走过的路。

从 A 出发：
A → B → D → （D 没有新邻居了，退回）→ 回到 A → C → （走过了，结束）

• 怎么实现？用栈（第 04 章！），或者更常见的是用递归（递归本质就是借用了系统的函数调用栈）。「一条道走到黑再回头」正是后进先出。
• 擅长：探索「所有可能性」、判断连通性、走迷宫找出所有路径、检测环、处理依赖顺序等。

  「有没有一条路能到达」「把所有走法都试一遍」——这类问题用 DFS。

BFS vs DFS 对照

看到没？前面学的队列和栈，在这里成了图遍历的引擎。这就是数据结构之间的呼应——基础结构是高级算法的零件。

小结

• 图的存储两种：邻接矩阵（大表格，查连通 O(1) 但费空间，适合边密）、邻接表（每点记邻居名单，省空间，适合边稀，最常用）。
• 图的遍历要记录访问过的点防止绕圈；两种走法：
  • BFS 广度优先：一圈圈向外扩，用队列实现，擅长最短路径/最少步数。
  • DFS 深度优先：一条路走到黑再回头，用栈/递归实现，擅长连通性、遍历所有可能、依赖排序。
• 栈和队列在这里成了图遍历的核心引擎——基础数据结构支撑起高级算法。

下一章 → 13 - 遇到问题该选哪种数据结构 ｜ 回到 README 目录