图数据结构表示方法：一张城市地图的四种画法

可视化演示

图的基本概念

交通局的第一天，老局长丢给你一张手绘地图：圆圈代表路口，线段代表道路，箭头代表单行道。他说：「这就是图。路口叫顶点，路叫边。你脑子里先别想什么矩阵链表，先搞清楚你记录的是什么东西。」你盯着地图，意识到两个路口之间有路是「无向边」（双向通行），而一条路只能单向走就是「有向边」——整张图就是由顶点和边构成的「关系档案」。

很快你发现，不同的城市长得完全不一样。老城区路口少，但几乎每个路口之间都有路相通，密密麻麻像一张网，这叫稠密图；新城区路口很多，可大部分路口之间根本没路，只有零星的几条主干道，这叫稀疏图。网格员还告诉你一个规律：每条路会被两端的路口各记录一次，所以所有路口的度数（连接它的道路数量）加起来，恰好是道路总数的两倍。

$$\sum_{v \in V} \deg(v) = 2|E|$$

1. 求和符号 Σ：把图中所有顶点的度数加起来。

$$\sum_{v \in V}$$

2. 度数 deg(v)：与顶点 v 相连的边数，相当于路口 v 连接的道路条数。

$$\deg(v)$$

3. 2|E|：边数乘以 2，因为每条无向边都会在两端各贡献一次度数。

$$2|E|$$

为什么这个性质重要？因为它是后面判断存储空间时反复用到的「账本原则」：你记录道路的方式，本质上就是在管理这些「双向计数」。搞懂了顶点、边、有向无向、稠密稀疏这四件事，你才能理解为什么有人用公告板、有人用路牌——不同城市的记录方案，天生就该不一样。

邻接矩阵

你决定先采用最直观的方案：在规划局大厅挂一块巨大的公告板。横轴是全部路口的编号，纵轴也是全部路口的编号，于是板子被分成了 n×n 个格子。格子 (i, j) 里打勾，表示路口 i 和路口 j 有路；空白则没有。这块「路口 × 路口」的公告板，就是邻接矩阵——一个二维数组，matrix[i][j] = 1 代表 i 到 j 有边，0 代表没有。

老局长来视察，一眼就爱上了这块板子。因为任何一个人来问「A 和 B 通不通」，你只需看一眼第 A 行第 B 列的格子，一步到位。在计算机里，这就是数组按下标随机访问，时间复杂度是常数时间 O(1)。可没过多久问题来了：老城区路口少还好说，新城一规划就是上万个路口，那块板子要挂整整一万乘一万的格子，其中绝大多数格子都是空的——整面墙都在「浪费白板」。

$$\text{空间复杂度} = O(n^2)$$

1. n 的含义：图中顶点的个数，即路口总数。

$$n$$

2. n² 的由来：矩阵有 n 行 n 列，共 n × n 个格子，每个格子存一个 0/1 标记。

$$n \times n$$

3. O 记号：表示存储量随 n 增长的「规模级」。n² 意味着当路口翻倍时，板子的面积要变成原来的 4 倍。

$$O(n^2)$$

所以邻接矩阵的结论是：查询快如闪电，但空间代价巨大。它只适合「老城区」——顶点不多、边足够稠密、格子填得满的稠密图。一旦顶点数量大而边稀疏，这块公告板就成了城市财政的无底洞，逼着你寻找更聪明的方案。

邻接表

你开始反思：为什么非要挂一块 n×n 的大板子？大部分格子明明空着。新方案是这样：不再集中管理，而是在每个路口立一块小牌子，牌子上只写「从这儿出去能到的路口编号」。牌子是块链板——第一块写着第一个邻居，旁边打个铁环拴住下一块，下一块又拴下下一块，直到写完所有能去的方向。这套「路口各管各的链板」，就是邻接表：一个长度为 n 的数组，数组每个元素是一条链表，链表中存的就是该顶点的全部邻居。

效率账本立刻好看了。全城总共需要多少块牌？路口本身 n 块牌，道路 e 条，每条路在起点处挂一块指向对方的牌，所以总共 n + e 块。对比邻接矩阵的 n²，当城市道路稀疏（e 远小于 n²）时，省下的空间相当可观。代价也有：问「A 和 B 通不通」时，你得翻遍 A 那块牌子上的所有邻居链，运气好排第一，运气差排最后——耗时和 A 的度数成正比。

$$\text{空间复杂度} = O(n + e)$$

1. n 个表头：每个路口一块「起始牌」，组成长度 n 的数组。

$$n$$

2. e 个边节点：每条边在起点链表里生成一个邻居节点，共 e 个。

$$e$$

3. n + e 总量：总存储单元是路口牌数加道路记录数，与 n² 相比在稀疏图中优势巨大。

$$n + e$$

邻接表完美解决了「新城路网稀疏」的痛点：牌子只在有路的地方立，没路的地方一块牌都不浪费。同时，遍历一个顶点的所有邻居变得极其自然——从头牌开始顺着铁环一路摸过去就行，后续学图搜索（BFS/DFS）时，这正是它备受宠爱的原因。但如果你遇到单行道密布的老城，邻接表还有个遗憾：你只记录了「出得去」，却很难快速回答「哪些路口能进得来」。

十字链表

有向图的世界里，「出」和「入」是两码事。单行道 A→B，意味着 A 的牌子要写 B，但 B 的路口若想让人知道「可以从 A 来」，还得另立一本「入城登记簿」。用邻接表时，你想找某个顶点的所有前驱，就得遍历全城的牌子——太慢了。于是聪明的工程师发明了十字链表：每个路口挂两块牌子，一块「出牌」记录能去的方向（出弧），一块「入牌」记录从哪来（入弧），中间用一道横梁钉在一起，两块牌子既各自成链，又通过路口节点互相索引。

更重要的是，这种结构对「动态改路」格外友好。施工队封一条单行道时，只要顺着该弧节点的出链和入链把它摘下来，两边的链表一接就完事，不需要像邻接矩阵那样改两个格子、也不用像邻接表那样翻半天。十字链表把「每条弧」做成一个独立登记对象，它身上同时携带弧头、弧尾、下一条出弧指针、下一条入弧指针——一张「弧的身份证」把出和入全记齐了。

$$\text{顶点结构：} v = \{ data,\ firstin,\ firstout \}$$

1. data 数据域：存顶点编号，相当于路口名。

$$data$$

2. firstin 入链指针：指向第一条「进入该顶点」的弧节点，即入弧链表头。

$$firstin$$

3. firstout 出链指针：指向第一条「从该顶点出发」的弧节点，即出弧链表头。

$$firstout$$

十字链表在空间上与邻接表同级（O(n+e)），却额外白送了「入边查找」和「高效的弧删除」。它就像给每个单行道路口配了「进口台账 + 出口台账」双本账，道路改向、封路都能快速翻到对应登记页。工程上，编译器分析代码依赖、搜索引擎做网页链接分析时，有向图的双向检索需求强烈，十字链表常常是幕后英雄。

邻接多重表

无向图也有自己的麻烦。你发现在邻接表里记录双向路时，一条路 A—B 被写了两次：A 的链上有 B，B 的链上也有 A。这倒不算浪费，可一旦要删除这条道路，你得同时去 A 和 B 两块牌子上找到对应的链节点，各摘一次——有点手忙脚乱。邻接多重表就是专门来治这个病的：每条无向边只做一个「登记牌」，牌子上写两个端点，并且在这个牌子身上挂两个指针圈：一个圈把「以 A 为一端的所有边」穿起来，另一个圈把「以 B 为一端的所有边」穿起来。

这样一来，A 和 B 的路牌上都不再各自复制一份边，大家共享同一个边对象，只是通过不同的指针「串门」。想删除 A—B 这条路？找到那张登记牌，同时解开两个指针圈，一条边就干净利落地消失了，绝不需要两头找、两头改。空间上它仍然是 O(n + e)，但因为边节点只存一次，常数系数比普通邻接表更小，像一个「去重版」的邻接表。

$$\text{边节点：} e = \{ mark,\ v_1,\ v_2,\ link_1,\ link_2 \}$$

1. mark 标记位：记录这条边是否被访问过，做遍历算法时有用。

$$mark$$

2. v₁ 与 v₂：无向边的两个端点路口。

$$v_1,\ v_2$$

3. link₁ 与 link₂：分别指向「依附于 v₁ 的下一条边」和「依附于 v₂ 的下一条边」，把同一条边的两条链串起来。

$$link_1,\ link_2$$

邻接多重表最迷人的地方在于「一物一牌」：它彻底解决了无向图中同一条边被重复登记的问题。当你的系统需要频繁增删边——比如社交网络的好友关系持续变化、路网维修调度不断切换——这种结构让每次操作都干净利落。它和十字链表互为镜像：一个管有向图的双向弧，一个管无向图的去重边。

对比分析

四张地图摊开在会议室桌上，老局长请你做个横向测评。先看空间：邻接矩阵无脑占用 n²，剩下三者都是 n + e 级别。再看查询：判断任两点是否相邻，矩阵一步到位 O(1)，而链表结构都得顺着链找，平均 O（度数）。可若问「遍历某个顶点的所有邻居」，链表结构直接顺着链往下读，矩阵却要扫一整行 n 个格子，反而慢。删除边的场景里，十字链表和邻接多重表因为有边对象和双链，删除效率远高于普通邻接表。

你把这些维度画成一张对比表，发现没有绝对王者，只有「谁更合身」。邻接矩阵像公告板，适合频繁查「通不通」、且图足够稠密的场景；邻接表像路口路牌，适合稀疏图、遍历邻居多的场景；十字链表是单行道城市的「出入双台账」；邻接多重表是双向路城市的「边登记处」。选择的关键词永远是：你的图多密？你的操作偏查询还是偏遍历？边会不会频繁增删？

| 表示方法 | 空间复杂度 | 查询两点相邻 | 遍历某点邻居 | 删除边 |

|---|---|---|---|---|

| 邻接矩阵 | O(n²) | O(1) | 较差（扫整行） | 一般 |

| 邻接表 | O(n+e) | 较慢（找链） | 快（直接读链） | 较慢（两头找） |

| 十字链表 | O(n+e) | 较慢 | 快 | 有向图高效 |

| 邻接多重表 | O(n+e) | 较慢 | 快 | 无向图高效 |

在 AI 工程里，这个「无绝对王者」的结论尤其重要：知识图谱的节点动辄上亿，选错表示方法，一次遍历查询可能从毫秒级退化到分钟级。理解每个方案的强项弱项，是后续所有图算法（PageRank、社区发现、GNN）的性能地基。

选型策略

最后一个问题：真到了工地上，该怎么拍板？你总结出一套口诀。第一步看密度：如果边数 e 接近 n²，说明图密得像渔网，直接上邻接矩阵——格子填得满，浪费少，查询还最快；如果 e 远小于 n²，邻接表立省千倍空间。第二步看操作：你的算法是反复问「A 连不连 B」，还是反复问「A 的所有邻居是谁」？前者矩阵胜，后者链表胜。第三步看动态性：边会频繁插入删除吗？会就考虑十字链表（有向）或邻接多重表（无向），它们把删除边的代价压到最低。

这套策略在真实世界中每天都在上演。大型图数据库 Neo4j 底层用类似邻接表的「免索引邻接」结构，就是为了让「查邻居」快如闪电；而在稠密的小规模子图上，工程师反而会临时构造邻接矩阵，用矩阵乘法并行加速。图神经网络（GNN）里，稀疏邻接表配合专用稀疏矩阵运算库，才能在千万节点上训练——这就是选型策略的力量：没有最好的表示，只有最合适的搭配。

当你日后面对一道算法题、一次系统设计面试，或一个真实的大规模图计算任务时，请回想今天在数字城市里学到的这节课：先摸清图的密度，再想清楚核心操作，最后考虑动态性。城市地图的四种画法，你已经全部收入囊中。

AI 应用场景

Python 演示

class GraphMatrix:    """邻接矩阵：n x n 的二维数组，arr[i][j] 为 1 表示 i 到 j 有边。"""     def __init__(self, n):        self.n = n        self.mat = [[0] * n for _ in range(n)]     def add_edge(self, u, v):        self.mat[u][v] = 1        self.mat[v][u] = 1     def space(self):        return self.n * self.n     def has_edge(self, u, v):        return self.mat[u][v] == 1  class GraphList:    """邻接表：n 个列表，adj[u] 里存 u 的所有邻居。"""     def __init__(self, n):        self.n = n        self.adj = [[] for _ in range(n)]     def add_edge(self, u, v):        self.adj[u].append(v)        self.adj[v].append(u)     def space(self):        return self.n + sum(len(x) for x in self.adj)     def has_edge(self, u, v):        return v in self.adj[u]  if __name__ == "__main__":    gm = GraphMatrix(6)    gl = GraphList(6)    edges = [(0, 1), (1, 2), (2, 5), (0, 3), (3, 4), (4, 5)]     for u, v in edges:        gm.add_edge(u, v)        gl.add_edge(u, v)     print("顶点数 n =", 6)    print("边数 e =", len(edges))    print("邻接矩阵占用单元:", gm.space())    print("邻接表占用单元:", gl.space())    print("查询边 (1, 4):", gm.has_edge(1, 4), gl.has_edge(1, 4))    print("查询边 (0, 2):", gm.has_edge(0, 2), gl.has_edge(0, 2))

1. self.mat = [[0] * n for _ in range(n)]生成 n 行 n 列的全零矩阵，模拟「公告板」的空白格子。
2. self.mat[u][v] = 1在公告板的 (u, v) 位置打勾，记录一条边。
3. def space(self):统计占用单元数，矩阵固定为 n²，能直观看到顶点增加时的爆炸式增长。
4. self.adj = [[] for _ in range(n)]创建 n 个空列表，每个列表就是一块「路口路牌」。
5. self.adj[u].append(v)在 u 的路牌上钉一块写有 v 的新链板。
6. self.n + sum(len(x) for x in self.adj)邻接表空间算的是「n 块路牌 + 所有链板总数」，对应 O(n+e)。
7. return v in self.adj[u]查询时顺着 u 的链板逐个找 v，体现了链式结构查询的耗时特性。
8. gm.has_edge(1, 4)对矩阵来说一次下标访问就出结果，与链表的线性查找形成鲜明对比。

常见误区

面试题