图-地图软件怎么存下千万条路？

数据结构与算法 · 图 · 第 02 篇

标签：#图 #邻接矩阵 #邻接表 #图的表示

预计阅读时间：12分钟

开篇-1万个城市，1亿条路

高德地图上存着全国所有城市和道路。城市数以万计，道路数以亿计。这些数据存在计算机里，不是画在纸上——计算机需要一种高效的方式来存储和访问图。

有两种主流方法：邻接矩阵和邻接表。它们就像同一份地图的两种画法，各有各的适用场景。今天我们就来聊聊这两种表示方法，搞清楚什么时候用哪种。

邻接矩阵：二维表格存图

邻接矩阵用一个 n×n 的二维数组表示图。matrix[i][j] = 1 表示顶点 i 和顶点 j 之间有边。用代码表示：

# 4个顶点A,B,C,Dn = 4matrix = [    [0, 1, 1, 0],  # A    [1, 0, 0, 1],  # B    [1, 0, 0, 1],  # C    [0, 1, 1, 0]   # D]# 检查A和B是否连通if matrix[0][1] == 1:print("A和B连通")

带权图的邻接矩阵，把1换成权重：

matrix = [    [0, 2, 3, 0],   # A到B代价2，A到C代价3    [2, 0, 0, 1],   # B到A代价2，B到D代价1    [3, 0, 0, 4],   # C到A代价3，C到D代价4    [0, 1, 4, 0]    # D到B代价1，D到C代价4]

邻接矩阵的优势：

• 查两点是否连通：O(1)，直接查表格
• 代码简单：二维数组，一看就懂

劣势：

• 空间浪费：n个顶点需要n²空间。1万个城市就要1亿个格子。如果城市之间大部分不相连（稀疏图），绝大部分格子存的是0
• 遍历某个顶点的所有邻居：O(n)，需要扫一整行

什么时候用邻接矩阵？顶点少、边密集（稠密图）的时候。

邻接表：链表存图

邻接表给每个顶点维护一个链表，只存它直接相连的邻居。

用代码表示：

graph = {'A': ['B', 'C'],'B': ['A', 'D'],'C': ['A', 'D'],'D': ['B', 'C']}# 带权版本graph_weighted = {'A': [('B', 2), ('C', 3)],'B': [('A', 2), ('D', 1)],'C': [('A', 3), ('D', 4)],'D': [('B', 1), ('C', 4)]}

邻接表的优势：

• 省空间：只存实际存在的边，空间O(n + m)，n是顶点数，m是边数
• 遍历邻居快：O(邻居数)，不需要扫一整行

劣势：

• 查两点是否连通：需要遍历链表，O(邻居数)
• 代码稍微复杂：需要处理链表/列表

什么时候用邻接表？顶点多、边少（稀疏图）的时候。

对比：地图软件选哪种

高德地图有上万个POI（兴趣点），但每个POI只和附近的几十个POI直接相连。这是一个典型的稀疏图——边数远小于n²。

如果用邻接矩阵：1万×1万 = 1亿个格子，每个格子4字节 = 400MB内存，绝大部分是0。

如果用邻接表：1万个顶点 + 几十万条边，总共几MB内存。

结论：地图软件用邻接表。 事实上，几乎所有工程应用都用邻接表，因为真实世界的图基本都是稀疏的。

邻接矩阵主要用于两种情况：

1. 图很小（n < 100），代码简单优先
2. 需要频繁查询"任意两点是否连通"（Floyd算法）

LeetCode 实战：找到所有路径（LeetCode 797）

题目：给你一个有向无环图，graph[i]是顶点i的所有邻居。找出从顶点0到顶点n-1的所有路径。

最直观的想法：从0出发，DFS走到每个邻居，记录路径，到达n-1时把路径加入结果。

defall_paths_source_target(graph):    n = len(graph)    result = []    path = [0]  # 从顶点0开始defdfs(node):# 到达终点？保存路径if node == n - 1:            result.append(path.copy())return# 遍历所有邻居for neighbor in graph[node]:            path.append(neighbor)            dfs(neighbor)            path.pop()  # 回溯    dfs(0)return result

这道题和图的表示的联系：题目给的graph就是邻接表格式，直接遍历graph[node]就能拿到所有邻居。如果用邻接矩阵，需要先扫一整行找邻居，效率低得多。

复杂度：时间O(2^n)，最坏情况路径数 exponentially 增长。空间O(n)，递归栈深度。

这里有几个坑：

1. path要用copy。result.append(path)存的是引用，path后续会变。result.append(path.copy())存的是快照。

2. 回溯别忘了pop。进入邻居前append，递归返回后pop，否则路径会越积越长。

3. 题目是无环图。如果有环，需要额外标记访问过的节点防止无限循环。

生活里的影子：旅行规划——从出发地到目的地，把所有可能的路线列出来。每到一个城市，看看下一站能去哪，走到终点就记录一条路线。

总结

金句：邻接矩阵像一张完整的表格——行列整齐，但大部分格子空着浪费。邻接表像每个人的通讯录——只存认识的人，不存全世界的人。真实世界的图大都是稀疏的，邻接表才是工程界的默认选择。

觉得有收获？转发给你的技术伙伴。

你平时写代码时，如果遇到一个图的问题，你会先想用邻接矩阵还是邻接表？如果图里有100万个节点但只有200万条边，选哪种更省内存？评论区聊聊你的选择。