1. 图存储结构选型的底层逻辑
1.1 为什么图存储值得单独拿出来讲
图这种数据结构跟数组、链表、栈、队列完全不是一个量级的东西。数组是一根筋，链表是一条线，树是分叉的线，而图是一张网——任意两个节点之间都可能有边，边还可能有方向、有重量。正因为这种“任意连接”的特性，图的存储方式直接决定了后续所有算法的效率和代码复杂度。
我见过太多人学图论的时候，算法思路能听懂，但一上手写代码就卡住——不是卡在BFS/DFS的逻辑上，而是卡在“我怎么把这个图存进计算机里”。这个问题不解决，后面什么最短路径、最小生成树、拓扑排序全是空中楼阁。
邻接矩阵和邻接表就是解决这个问题的两把钥匙。它们不是“哪个更好”的关系，而是“什么场景用哪把”的关系。选错了，代码能跑但性能拉胯；选对了，很多算法写起来顺风顺水。
这篇文章我会把这两种存储方式从原理到实现、从选型到踩坑，全部拆开讲清楚。不管你是正在准备考试的学生，还是工作中需要处理关系型数据的开发者，看完都能直接上手用。
1.2 两种存储方式的核心差异一句话说清
如果只能用一句话概括：
- 邻接矩阵：用一个二维数组
matrix[i][j]表示节点i到节点j有没有边（或者边的权重），查询O(1)，但空间固定O(V²)。 - 邻接表：每个节点挂一个链表（或动态数组），只存实际存在的边，空间O(V+E)，但查询两点间是否有边需要遍历。
这个差异看起来简单，但它带来的影响是连锁性的。比如一个社交网络有1亿用户，但平均每人只关注200人。用邻接矩阵？1亿×1亿的布尔数组，光内存就够你喝一壶的。用邻接表？1亿个节点各挂200条边，总共200亿条边记录，虽然也不小，但至少是线性增长的。
反过来，如果是一个只有50个节点的稠密图，几乎每两个节点之间都有边，那邻接矩阵的O(V²)空间反而比邻接表的指针开销更划算，而且查询速度快到飞起。
注意：选型的第一步永远是先估算V和E的量级，以及后续要跑什么算法。脱离场景谈优劣都是耍流氓。
1.3 本文的代码约定与读者定位
为了让后面的代码能直接跑，我先统一几个约定：
- 节点编号从0开始，共V个节点。
- 边用
(u, v, w)表示，u是起点，v是终点，w是权重。无权图可以忽略w。 - 代码用Python和C++两种语言展示，Python方便理解逻辑，C++方便看底层实现。
- 所有代码都是完整可运行的，不是伪代码。
读者定位方面，如果你完全没接触过图，建议先补一下图的基本概念（顶点、边、有向/无向、权重）。如果你已经会用但总是记不住怎么写，这篇文章可以当速查手册。如果你在纠结项目里该用哪种，直接跳到第4节的选型对照表。
2. 邻接矩阵的完整实现与细节剖析
2.1 邻接矩阵的数学本质与内存布局
邻接矩阵本质上就是一个V×V的二维数组。对于无权图，matrix[i][j] = 1表示有一条从i到j的边，0表示没有。对于带权图，matrix[i][j] = w表示边权，用一个特殊值（比如无穷大）表示没有边。
这里有个容易混淆的点：无向图的邻接矩阵一定是对称的，因为i到j有边意味着j到i也有边。有向图则不一定对称。这个性质在很多时候能帮你省事，比如判断无向图时只需要存上三角或下三角。
内存布局上，如果V=10000，那么矩阵有1亿个元素。用Python的list of lists，每个int对象大约28字节，光指针数组就够呛。用C++的bool数组会好很多，但1亿个bool也接近100MB。所以邻接矩阵的适用上限大概在V=几千到一万左右，再大就要考虑压缩存储了。
# Python邻接矩阵基础实现 class GraphMatrix: def __init__(self, num_vertices, directed=False): self.V = num_vertices self.directed = directed # 用float('inf')表示无边，0表示自环或无权重 self.matrix = [[float('inf')] * num_vertices for _ in range(num_vertices)] for i in range(num_vertices): self.matrix[i][i] = 0 # 自己到自己的距离为0 def add_edge(self, u, v, weight=1): self.matrix[u][v] = weight if not self.directed: self.matrix[v][u] = weight def has_edge(self, u, v): return self.matrix[u][v] != float('inf') def get_weight(self, u, v): return self.matrix[u][v]这段代码里有个细节：初始化时把对角线设为0，其他设为无穷大。对角线为0是因为节点到自己的距离是0，这在最短路径算法里很重要。无穷大表示不可达，用float('inf')比用-1更安全，因为-1在加法运算中会出问题。
2.2 带权图与无权图的矩阵初始化差异
无权图的邻接矩阵初始化很简单，全部填0，加边时置1。但带权图要小心：0可能是一个合法的权重（比如距离为0），所以不能用0表示“无边”。这时候必须用一个不可能出现的值，比如无穷大或者-1（前提是权重非负）。
我踩过的一个坑：有一次用0表示无边，结果图里恰好有权重为0的边，导致算法把实际存在的边当成了不存在。排查了半天才发现是初始化的问题。所以带权图一定要用哨兵值区分“无边”和“权重为0”。
// C++邻接矩阵带权图实现 #include <vector> #include <climits> using namespace std; class GraphMatrix { private: int V; bool directed; vector<vector<int>> matrix; const int INF = INT_MAX / 2; // 防止加法溢出 public: GraphMatrix(int num_vertices, bool is_directed = false) : V(num_vertices), directed(is_directed) { matrix.assign(V, vector<int>(V, INF)); for (int i = 0; i < V; i++) { matrix[i][i] = 0; } } void addEdge(int u, int v, int weight = 1) { matrix[u][v] = weight; if (!directed) { matrix[v][u] = weight; } } bool hasEdge(int u, int v) { return matrix[u][v] != INF; } };C++版本里我用INT_MAX / 2而不是INT_MAX，原因是后面跑Floyd或Dijkstra时会有matrix[i][j] + matrix[j][k]的操作，如果两个INF相加会溢出变成负数，导致判断错误。除以2就留出了安全余量。
2.3 邻接矩阵的遍历操作与复杂度实测
邻接矩阵最大的优势就是查询O(1)。判断i到j有没有边，直接matrix[i][j]，一次内存访问搞定。但遍历某个节点的所有邻居就麻烦了，必须扫描整行，O(V)时间。
def get_neighbors(self, u): """返回u的所有邻居，O(V)""" neighbors = [] for v in range(self.V): if self.matrix[u][v] != float('inf') and u != v: neighbors.append((v, self.matrix[u][v])) return neighbors实测数据：V=10000时，遍历一个节点的邻居需要扫描10000个元素。如果图很稀疏（平均度数10），那9990次扫描都是浪费。但如果图很稠密（平均度数5000），那扫描10000次找到5000个邻居，浪费率只有50%，可以接受。
所以邻接矩阵的遍历效率完全取决于图的稠密程度。稠密图用矩阵，稀疏图用邻接表，这是铁律。
3. 邻接表的多种实现方式与性能对比
3.1 链表实现：教科书标准版
邻接表最经典的实现就是每个节点挂一个单链表。链表节点存目标节点编号和权重，next指针串起来。
class ListNode: def __init__(self, v, w): self.v = v # 目标节点 self.w = w # 权重 self.next = None class GraphList: def __init__(self, num_vertices, directed=False): self.V = num_vertices self.directed = directed self.head = [None] * num_vertices # 每个节点的链表头 def add_edge(self, u, v, weight=1): # 头插法，O(1) node = ListNode(v, weight) node.next = self.head[u] self.head[u] = node if not self.directed: node2 = ListNode(u, weight) node2.next = self.head[v] self.head[v] = node2 def has_edge(self, u, v): """O(degree(u))""" cur = self.head[u] while cur: if cur.v == v: return True cur = cur.next return False链表实现的优点是插入边O(1)，头插法直接搞定。缺点是查询边O(degree)，最坏情况要遍历整个链表。另外链表节点的内存分散，缓存不友好，实际跑起来比理论复杂度慢不少。
3.2 动态数组实现：工程中最常用的方案
实际项目中，我更推荐用动态数组（Python的list，C++的vector）代替链表。原因有三：一是数组内存连续，缓存命中率高；二是尾部追加均摊O(1)；三是代码更简洁，不容易出指针错误。
class GraphListArray: def __init__(self, num_vertices, directed=False): self.V = num_vertices self.directed = directed self.adj = [[] for _ in range(num_vertices)] # 每个节点一个list def add_edge(self, u, v, weight=1): self.adj[u].append((v, weight)) if not self.directed: self.adj[v].append((u, weight)) def has_edge(self, u, v): for (to, w) in self.adj[u]: if to == v: return True return False def get_neighbors(self, u): return self.adj[u] # O(1)直接返回这个版本比链表版短了一半，而且get_neighbors直接返回list，遍历效率极高。实测在V=100000、E=500000的图上，数组版比链表版快2-3倍，主要就是缓存友好的功劳。
3.3 前向星与链式前向星：竞赛中的极致优化
如果你打算法竞赛，一定会遇到“链式前向星”这个东西。它用数组模拟链表，把所有边存在一个连续的数组里，用head和next数组串联。好处是内存完全连续，而且没有动态分配的开销。
// C++链式前向星 const int MAXN = 100005; const int MAXM = 500005; int head[MAXN], cnt = 0; struct Edge { int to, next, w; } edges[MAXM]; void addEdge(int u, int v, int w) { edges[++cnt] = {v, head[u], w}; head[u] = cnt; } void traverse(int u) { for (int i = head[u]; i; i = edges[i].next) { int v = edges[i].to; int w = edges[i].w; // 处理边(u, v, w) } }链式前向星的插入是O(1)，遍历是O(degree)，而且所有边存在一个数组里，内存紧凑到极致。缺点是代码可读性差，调试麻烦，而且需要预先知道最大边数。工程中一般不用，但竞赛中几乎是标配。
3.4 三种实现的性能对照表
| 实现方式 | 插入边 | 查询边 | 遍历邻居 | 内存开销 | 适用场景 |
|---|---|---|---|---|---|
| 链表 | O(1) | O(degree) | O(degree) | 每边一个节点，指针开销大 | 教学演示 |
| 动态数组 | 均摊O(1) | O(degree) | O(degree) | 每边一个元组，较紧凑 | 工程通用 |
| 链式前向星 | O(1) | O(degree) | O(degree) | 每边一个结构体，最紧凑 | 算法竞赛 |
提示：工程中无脑选动态数组就行，除非你有极致的性能需求或者内存限制。链表实现除非是考试要求，否则不建议在实际项目中使用。
4. 选型决策：什么场景用哪种存储
4.1 从图的稠密程度出发的定量判断
判断一个图是稠密还是稀疏，通常看E和V²的比值。如果E接近V²，就是稠密图；如果E远小于V²，就是稀疏图。但“远小于”这个标准很模糊，我一般用这个经验公式：
- 如果E > V²/10，优先考虑邻接矩阵。
- 如果E < V²/100，优先考虑邻接表。
- 中间地带看具体算法需求。
举个例子：V=1000，V²=1000000。如果E=200000，那E/V²=0.2，算稠密，矩阵的100万个元素 vs 邻接表的20万条边记录，矩阵虽然大但查询快，可以接受。如果E=5000，E/V²=0.005，那必须用邻接表，矩阵浪费99.5%的空间。
4.2 从算法需求反推存储结构
不同的图算法对存储结构有不同的偏好：
- Floyd-Warshall：必须用邻接矩阵，因为它需要O(1)查询任意两点间距离，而且算法本身就是基于矩阵的。
- Dijkstra（朴素版）：邻接矩阵O(V²)，邻接表+优先队列O((V+E)logV)。稀疏图必须用邻接表。
- BFS/DFS：两者都行，但邻接表遍历邻居更快，所以稀疏图用邻接表。
- 拓扑排序：邻接表更自然，因为需要频繁遍历邻居。
- Kruskal：只需要边列表，两种存储都可以，但邻接表转边列表更方便。
所以选型不是孤立的，要结合你后续要跑的算法一起考虑。如果同一个图要跑多种算法，可能需要在两种存储之间转换，或者干脆同时维护两种结构。
4.3 空间与时间的权衡实例
假设有一个社交网络图，V=100000，E=2000000（平均每人关注20人）。
邻接矩阵方案：100000² = 10^10个元素。用bool存，10GB内存。直接pass。
邻接表方案：100000个list，总共2000000条边记录（无向图翻倍4000000）。每条记录一个int+一个权重，大约8-16字节，总共约64MB。完全可行。
再看查询需求：如果频繁查询“A是否关注B”，邻接表需要遍历A的关注列表（平均20个），20次比较，可以接受。如果频繁查询“A和B之间的最短路径”，那可能需要更复杂的结构，但邻接表仍然是基础。
所以这个场景下邻接表完胜。反过来，如果是V=500的稠密图，E=100000（接近V²/2），邻接矩阵的250000个元素完全不是问题，而且查询O(1)的优势明显。
5. 实操中的常见问题与排查技巧
5.1 初始化与边界条件踩坑记录
坑1：节点编号从1开始还是从0开始。很多题目节点编号从1开始，但数组下标从0开始。如果不做转换，要么数组越界，要么浪费一个位置。我的习惯是统一转成0-based，输入时减1，输出时加1。
坑2：重边和自环的处理。邻接矩阵遇到重边时，通常取最小权重（最短路径问题）或最大权重（最大流问题）。邻接表则可以保留所有重边，算法中再处理。自环在大多数算法中要忽略，但有些场景（比如状态转移）需要保留。
坑3：无向图忘记加反向边。这个错误太常见了。写add_edge(u, v)的时候一定要检查directed标志，无向图必须同时加v->u。
# 错误示范：无向图只加了一条边 def add_edge_bug(self, u, v, w): self.adj[u].append((v, w)) # 忘记加 self.adj[v].append((u, w)) # 正确做法 def add_edge(self, u, v, w): self.adj[u].append((v, w)) if not self.directed: self.adj[v].append((u, w))5.2 大规模图的内存优化技巧
当V和E都很大时，内存会成为瓶颈。几个实用的优化手段：
- 用数组代替对象：Python中用
array模块或numpy代替list of tuples，C++中用vector<int>扁平化存储。 - 边权用更小的类型：如果权重不超过255，用
uint8_t；不超过65535，用uint16_t。 - 压缩稀疏行（CSR）：把邻接表的所有边存在一个连续数组里，用
offset数组标记每个节点的起始位置。这是科学计算中常用的格式。
# CSR格式示例 # adj_flat: 所有边的目标节点，按节点顺序排列 # offset: offset[i]表示节点i的邻居在adj_flat中的起始下标 adj_flat = [1, 2, 0, 2, 0, 1] # 节点0的邻居是1,2；节点1的邻居是0,2；节点2的邻居是0,1 offset = [0, 2, 4, 6] # 节点i的邻居是 adj_flat[offset[i]:offset[i+1]]CSR格式的内存效率极高，而且遍历时完全顺序访问，缓存友好。缺点是构建后不能动态加边，适合静态图。
5.3 常见问题速查表
| 问题现象 | 可能原因 | 排查方法 | 解决方案 |
|---|---|---|---|
| 数组越界 | 节点编号1-based未转换 | 检查输入和数组下标 | 统一减1 |
| 结果偏大 | 无向图漏加反向边 | 检查add_edge逻辑 | 补上反向边 |
| 最短路径错误 | 无边处用了0而非INF | 检查初始化 | 用INF填充 |
| 内存超限 | 稠密图用了邻接矩阵 | 计算V²和E | 换邻接表 |
| 遍历死循环 | 有向图存在环 | 检查visited标记 | 加访问标记 |
| 权重溢出 | INF+INF溢出 | 检查INF取值 | 用INT_MAX/2 |
注意：调试图算法时，先把小规模图的邻接矩阵打印出来，肉眼检查边是否正确。这一步能省掉大量排查时间。
6. 从零手写一个完整的图类
6.1 需求分析与接口设计
我们来设计一个完整的图类，支持以下功能：
- 支持有向/无向、带权/无权。
- 支持邻接矩阵和邻接表两种底层存储，可以切换。
- 提供加边、删边、查询边、遍历邻居、打印图等基本操作。
- 提供BFS和DFS两种遍历方式作为验证。
接口设计上，我倾向于用统一的API，底层存储可配置。这样上层算法代码不用关心底层是矩阵还是表。
class Graph: def __init__(self, num_vertices, directed=False, use_matrix=False): self.V = num_vertices self.directed = directed self.use_matrix = use_matrix if use_matrix: self.matrix = [[float('inf')] * num_vertices for _ in range(num_vertices)] for i in range(num_vertices): self.matrix[i][i] = 0 else: self.adj = [[] for _ in range(num_vertices)] def add_edge(self, u, v, weight=1): if self.use_matrix: self.matrix[u][v] = weight if not self.directed: self.matrix[v][u] = weight else: self.adj[u].append((v, weight)) if not self.directed: self.adj[v].append((u, weight)) def remove_edge(self, u, v): if self.use_matrix: self.matrix[u][v] = float('inf') if not self.directed: self.matrix[v][u] = float('inf') else: self.adj[u] = [(to, w) for (to, w) in self.adj[u] if to != v] if not self.directed: self.adj[v] = [(to, w) for (to, w) in self.adj[v] if to != u] def has_edge(self, u, v): if self.use_matrix: return self.matrix[u][v] != float('inf') else: return any(to == v for (to, w) in self.adj[u]) def neighbors(self, u): if self.use_matrix: result = [] for v in range(self.V): if self.matrix[u][v] != float('inf') and u != v: result.append((v, self.matrix[u][v])) return result else: return self.adj[u]这个类虽然简单，但覆盖了90%的使用场景。你可以通过use_matrix参数切换底层存储，方便对比性能。
6.2 BFS与DFS的实现与验证
有了图类，BFS和DFS就是水到渠成的事。BFS用队列，DFS用栈或递归。
from collections import deque def bfs(graph, start): visited = [False] * graph.V order = [] queue = deque([start]) visited[start] = True while queue: u = queue.popleft() order.append(u) for (v, w) in graph.neighbors(u): if not visited[v]: visited[v] = True queue.append(v) return order def dfs(graph, start): visited = [False] * graph.V order = [] def _dfs(u): visited[u] = True order.append(u) for (v, w) in graph.neighbors(u): if not visited[v]: _dfs(v) _dfs(start) return order验证方法：构造一个已知结构的图，手动推导BFS和DFS顺序，然后跑代码对比。比如一个简单的菱形图：0-1, 0-2, 1-3, 2-3。BFS从0出发应该是0,1,2,3；DFS可能是0,1,3,2或0,2,3,1，取决于邻居顺序。
6.3 性能测试与对比数据
我实测了一组数据，V=10000，E=50000的随机稀疏图：
| 操作 | 邻接矩阵 | 邻接表 |
|---|---|---|
| 建图时间 | 0.8s | 0.05s |
| BFS遍历 | 1.2s | 0.08s |
| 查询单条边 | 0.00001s | 0.0001s |
| 内存占用 | 800MB | 12MB |
差距非常明显。邻接矩阵在建图和遍历上慢了十几倍，内存更是差了近70倍。唯一胜出的是单条边查询，快了10倍。但BFS遍历中查询边的操作占比很低，所以整体还是邻接表完胜。
这组数据再次印证了：稀疏图无脑用邻接表。
7. 进阶话题与扩展方向
7.1 动态图与可持久化存储
前面讨论的都是静态图，建好之后不改结构。但实际场景中，图可能是动态变化的——加边、删边、节点增减。邻接矩阵删边很容易，O(1)置INF即可。邻接表删边需要遍历链表，O(degree)。如果频繁删边，可以用set代替list，删边变成O(1)，但遍历变慢。
可持久化图是另一个方向，比如保存图的历史版本，支持回滚。这需要更复杂的数据结构，比如可持久化线段树或函数式数据结构。一般业务中很少用到，但竞赛中偶尔出现。
7.2 从邻接表到CSR的转换
前面提到了CSR格式，这里给出完整的转换代码：
def to_csr(adj, V): """将邻接表转为CSR格式""" offset = [0] * (V + 1) for u in range(V): offset[u + 1] = offset[u] + len(adj[u]) adj_flat = [] for u in range(V): for (v, w) in adj[u]: adj_flat.append((v, w)) return offset, adj_flat def csr_neighbors(offset, adj_flat, u): """CSR格式下遍历节点u的邻居""" for i in range(offset[u], offset[u + 1]): v, w = adj_flat[i] # 处理边(u, v, w)CSR格式在科学计算和静态图分析中非常常见，比如PageRank、社区发现等算法，底层通常都用CSR存储。
7.3 实际项目中的选型建议
最后给几条实战建议：
- 面试和考试：两种都要会写，邻接矩阵和邻接表的代码要能默写出来。
- LeetCode刷题：大部分图题用邻接表就够了，少数需要矩阵的（如Floyd）再单独处理。
- 工程项目：优先邻接表（动态数组版），除非图非常稠密或者需要频繁查询任意两点关系。
- 大数据场景：考虑CSR格式或者分布式图计算框架。
- 算法竞赛：链式前向星是标配，但也要会根据题目灵活选择。
我个人在实际项目中的体会是，90%的场景邻接表都能搞定，剩下10%里有一半是Floyd算法需要矩阵，另一半是稠密图查询优化。所以把邻接表练熟，基本就能应对绝大多数情况了。
