在数据结构里图一直是我觉得“入门容易、深入难”的东西。链表、树好歹有个明显的层次或先后顺序但图不一样它允许任意两个顶点之间都有关系这种灵活性让它在社交网络、路径规划、推荐系统里无处不在。今天想聊的不是图的各种花哨算法而是最基础也最要命的一步——图的构建。如果你用过邻接矩阵或者邻接表你一定明白后面所有的高级操作比如最短路径、拓扑排序全都建立在一个“构建得对不对”的图之上。构建错了算法写得再漂亮也是白搭。这篇内容适合正在学数据结构的学生、准备面试的开发者以及那些想自己动手实现一个图结构但被“二维数组还是链表数组”纠结半天的朋友们。我会从存储结构选型讲起用Python手把手写出邻接矩阵和邻接表再把构建过程中的常见坑和排查思路一并倒出来。不整虚的全是实操。1. 内容整体设计与思路拆解1.1 图的基本定义与“构建”到底在做什么先统一一下认知。图由两部分组成顶点集合 V 和边集合 E。边可以是有向的也可以是无向的可以带权重也可以不带。构建图本质上就是把这套集合关系用一种计算机能存、能查、能改的方式落地。很多人觉得构建图不就是“存边”吗其实没这么简单。你在内存里怎么组织这些顶点和边直接决定了后面遍历、搜索的性能。比如说你手里有 10000 个顶点和 50000 条边用邻接矩阵会开出一个 10000×10000 的二维数组光空间就是 800MB如果用整数型而用邻接表只需要存 50000 个边节点内存消耗可能只有几十MB。这个差异在稍大规模的图上就会直接卡死程序。所以构建图的第一步不是写代码而是想清楚你的图是什么形态、规模多大、主要做什么操作。这才是“整体设计”的核心。我在带实验课的时候经常看到同学拿到题目就开始写邻接矩阵也不管顶点数量最后建一个 10 万×10 万的矩阵把内存撑爆。这就是没做设计。1.2 为什么邻接矩阵和邻接表能成为主流方案市面上图存储方案不少有邻接矩阵、邻接表、十字链表、邻接多重表等等但绝大多数教学和工程场景你只需要掌握前两个剩下的是针对特殊需求的优化版。邻接矩阵的思路非常直观开一个 N×N 的二维数组matrix[i][j] 为 1 表示顶点 i 到 j 有一条边为 0 表示没有。对于带权图直接把矩阵里的值替换成权重用无穷大表示“不可达”。这种结构最大的优势是查询一条边是否存在是 O(1) 时间复杂度写起来也顺手Python 里一个双层列表就搞定。邻接表则换了一种思路每个顶点对应一个链表Python里常用 list链表里存的是与它相邻的顶点。整体看起来像一个数组加链表的组合。它的优势是空间效率高对于稀疏图边远少于顶点平方存储开销小得多同时遍历某个顶点的所有邻居时复杂度是 O(度)不用像邻接矩阵那样扫一整行 N 个格子。至于怎么选我自己总结的经验就三条顶点少几百以内且要频繁判断两点是否连通用邻接矩阵顶点多、边稀疏或者需要频繁遍历邻居用邻接表如果是考试或作业写着练手选你最有把握的那一个但心里要清楚另一个的缺陷在哪。2. 核心细节解析与实操要点2.1 邻接矩阵构建中的维度、对称性与编码细节邻接矩阵虽然简单但细节里全是坑。先说维度。假设图里有 V 个顶点你需要一个 V×V 的矩阵。在 Python 里最经典的错误是用[[0] * V] * V来初始化。这种行为会造成每行引用同一个列表对象表面看是二维数组实际改一个元素整列都跟着变。正确做法是[[0]*V for _ in range(V)]列表推导式生成独立行。接下来是顶点编号问题。现实中顶点可能是字符串比如城市名、用户ID你要先做一次映射把字符串转成 0 到 V-1 的整数索引。我见过不少同学忘了这步直接拿字符串当下标程序瞬间报错。构建前先建立一个字典例如{北京:0, 上海:1}后续所有操作都基于数字下标这既能提速也方便和邻接表统一。对于无向图矩阵是对称的。也就是说添加一条边 u-v 时你得同时设置matrix[u][v]1和matrix[v][u]1。漏掉任意一边都算图没建全。对于有向图则只设前者。带权图同理给对应位置赋权重无穷大一般用float(inf)或一个足够大的数比如 99999不推荐用负数不然后面的最短路径算法会直接懵圈。还有一个小细节自环和重边。自环就是顶点连自己矩阵里的对角线元素。多数算法允许自环但对角线设成 1 还是 0 取决于问题语义。重边在简单图里一般忽略矩阵天然只记录一条边。如果你用的是邻接表就需要注意重复添加的问题。2.2 邻接表构建中的链表结构与动态扩容技巧邻接表的 Python 实现我推荐用“列表套列表”或者“列表套字典”。列表套列表就是adj [[] for _ in range(V)]然后adj[u].append(v)。如果你想同时存权重可以改成adj[u].append((v, w))或者直接用字典套列表adj {i:[] for i in range(V)}。这里有一个很多人忽略的点邻接表的顶点顺序默认是“插入顺序”而你后续做深度优先搜索DFS时遍历邻居的先后会直接影响搜索路径。如果题目要求按编号升序访问邻居你必须在插入后排序或者在构建时就按需插入。比如adj[u].append(v)之后调用adj[u].sort()别小看这步很多路径题的结果对顺序敏感。另一个问题是“无向图双向插入”。用邻接表时添加无向边 u-v 必须执行两次 appendadj[u].append(v)和adj[v].append(u)。漏掉一次图就变成了有向图你在 DFS 时就会漏顶点。我在调试学生的代码时超过一半的“漏点”问题都出在这一行上。空间优化方面如果你预先知道边的数量可以用reserve思想提前分配好容量。不过 Python 里的 list 自动扩容已经很高效平时写不用太纠结。真正要留意的是极限值当 V 有 10 万级别时邻接表的创建要避免使用{i:[] for i in range(V)}这种纯 Python 循环可以改用defaultdict(list)语义上更安全同时初始化速度也更快。3. 实操过程与核心环节实现3.1 从零开始构建一个无向无权图完整代码与分步说明我直接给出一套我自己常用的构建模板。假设输入是顶点列表[A,B,C,D]边列表[(A,B),(B,C),(C,D),(D,A)]。第一步建映射第二步建邻接表第三步顺手建个邻接矩阵做交叉验证。vertices [A, B, C, D] edges [(A, B), (B, C), (C, D), (D, A)] # 1. 顶点映射 index {v: i for i, v in enumerate(vertices)} n len(vertices) # 2. 邻接矩阵初始化 matrix [[0] * n for _ in range(n)] # 3. 邻接表初始化 adj [[] for _ in range(n)] # 4. 构建 for u, v in edges: i, j index[u], index[v] matrix[i][j] 1 matrix[j][i] 1 # 无向图对称 adj[i].append(j) adj[j].append(i) print(邻接矩阵:) for row in matrix: print(row) print(邻接表:) for i in range(n): print(f{vertices[i]}: {[vertices[j] for j in adj[i]]})运行结果非常直观矩阵是 4×4 的对称 0/1 数组邻接表则每个顶点都能列出自己的邻居。这套代码里映射表的构建是核心——没有 index 字典后面边列表没法快速定位。如果你换一种输入方式比如直接给定的是整数顶点编号可以省掉映射环节但实际业务里极少有这种好事所以映射一定要写好。带权图也很容易扩展把矩阵的1改成权重把邻接表的整数邻居改成元组例如(v, weight)。后面跑 Dijkstra 的时候邻接表遍历邻居取权重就非常顺手。这里提醒一下无向带权图一样要添加两次权重相同别写错。3.2 深度优先与广度优先遍历构建之后的第一件事图构建好了下一步通常是验证连通性。遍历算法就是最直接的验证器。我提供两个标准实现都用上面构建出来的邻接表。def dfs(adj, start, visited): visited[start] True print(start, end ) for neighbor in adj[start]: if not visited[neighbor]: dfs(adj, neighbor, visited) def bfs(adj, start): from collections import deque visited [False] * len(adj) q deque([start]) visited[start] True while q: node q.popleft() print(node, end ) for neighbor in adj[node]: if not visited[neighbor]: visited[neighbor] True q.append(neighbor)DFS 用递归虽然写起来简洁但顶点多时容易栈溢出。我在实战里更推荐显式栈版本用 list 模拟。BFS 用标准库的 deque时间复杂度 O(VE)空间也稳定。遍历顺序跟邻接表存储顺序强相关所以刚刚强调的“排序”在这一步就体现出来了想要稳定的结果最好维护一个有序邻居表。另外提一个容易忽略的测试技巧构建完图你可以随机挑一个起点跑 BFS然后用visited数组看看是否所有顶点都被访问到。如果有没有访问到的要么是非连通图要么是你的双向边漏加了一条。这个测试比肉眼检查矩阵快得多。4. 常见问题与排查技巧实录4.1 构建过程中最常出现的四类错误我统计过自己带实验课时遇到的大部分问题集中在四个地方。第一是数组初始化错误也就是刚才说的[[0]*n]*n导致共享引用。这个错误很隐蔽因为打印出来看是正常的只有当你赋值matrix[0][1]1时会发现matrix[1][1]也跟着变成了 1直接怀疑人生。排查方法很简单打印每个子列表的id看是否相同。第二是映射遗漏。顶点列表里有多个相同名字或者输入边列表里出现了顶点列表之外的顶点导致KeyError。解决方法是先做一个集合去重校验assert set(edges).issubset(set(vertices))但注意 edge 里每个元素可能是元组得展开判断。第三是无向图只加一边。这个错误在邻接表里表现得尤其明显A 能访问 BB 访问不到 A。你用 BFS 遍历时会发现图变成了“单向流动”的结构。简单验证方式是检查矩阵是否对称或者对每条边都执行assert v in adj[u] and u in adj[v]。第四是索引越界。顶点编号习惯从头开始用 1 的话矩阵就要开(n1)×(n1)用 0 下标则一切正常。很多刷题的代码默认顶点从 0 开始但实际场景偏偏从 1 开始。我的建议是无论题目怎么给统一内部转换成 0 基索引外部展示时再加1。4.2 性能调优与扩容经验当图不再“小而美”如果你只是做课程实验前面的代码已经够用。但一旦图规模上升到万级、十万级顶点你就得考虑更优的构建方式。邻接表里用 Python list 存邻居append 摊还时间复杂度是 O(1)可以接受。但如果你频繁做“判断两点是否相邻”的操作邻接表就要遍历列表那就不合算了。这时可以考虑在邻接表内部用 set 来存邻居查询复杂度降到 O(1)构建速度稍慢但整体更稳。邻接矩阵也有优化空间。稀疏图里矩阵全是 0你当然不想存一个巨大表格。如果你的内存很紧张可以考虑用一行位的字符串或者压缩数组来表示矩阵但代码复杂度会直线上升。课程设计里不建议这么折腾明白原理就行。我还想分享一个工程经验构建大图时尽量别反复调用 append 单个节点。可以先收集边到一个列表然后用批量方式构建。比如用for u, v in edges从文件读取时一次性使用adj[u].append(v)这个操作在 Python 里已经很快但如果你卡在性能上可以把所有边先按起点排序再统一构造链表结构。有点像是把杂乱的输入整理成索引数组这个思路在 C/C 里特别常见因为手动管理内存省了很多空节点分配。说实话图的构建写起来不难但“构建得好”需要你理解存储结构的本质。邻接矩阵胜在速度和直观邻接表胜在空间和遍历效率。你如果能把两种都写熟练再去看那些复杂的图算法就会觉得底层非常扎实。我个人在实际操作里最常用的其实是“邻接表 字典映射”的组合既方便调试又能应对大部分场景。最后分享一个小技巧写完构建代码后不要急着写算法先用小规模图比如 4 个顶点画一遍手推的邻接表和矩阵跟程序输出对一下。这个习惯帮我省下过太多排错时间。等图结构确认没问题再往上叠加拓扑排序、最短路径那些心里就特别有底。
从零构建图结构：邻接矩阵与邻接表的Python实现
在数据结构里图一直是我觉得“入门容易、深入难”的东西。链表、树好歹有个明显的层次或先后顺序但图不一样它允许任意两个顶点之间都有关系这种灵活性让它在社交网络、路径规划、推荐系统里无处不在。今天想聊的不是图的各种花哨算法而是最基础也最要命的一步——图的构建。如果你用过邻接矩阵或者邻接表你一定明白后面所有的高级操作比如最短路径、拓扑排序全都建立在一个“构建得对不对”的图之上。构建错了算法写得再漂亮也是白搭。这篇内容适合正在学数据结构的学生、准备面试的开发者以及那些想自己动手实现一个图结构但被“二维数组还是链表数组”纠结半天的朋友们。我会从存储结构选型讲起用Python手把手写出邻接矩阵和邻接表再把构建过程中的常见坑和排查思路一并倒出来。不整虚的全是实操。1. 内容整体设计与思路拆解1.1 图的基本定义与“构建”到底在做什么先统一一下认知。图由两部分组成顶点集合 V 和边集合 E。边可以是有向的也可以是无向的可以带权重也可以不带。构建图本质上就是把这套集合关系用一种计算机能存、能查、能改的方式落地。很多人觉得构建图不就是“存边”吗其实没这么简单。你在内存里怎么组织这些顶点和边直接决定了后面遍历、搜索的性能。比如说你手里有 10000 个顶点和 50000 条边用邻接矩阵会开出一个 10000×10000 的二维数组光空间就是 800MB如果用整数型而用邻接表只需要存 50000 个边节点内存消耗可能只有几十MB。这个差异在稍大规模的图上就会直接卡死程序。所以构建图的第一步不是写代码而是想清楚你的图是什么形态、规模多大、主要做什么操作。这才是“整体设计”的核心。我在带实验课的时候经常看到同学拿到题目就开始写邻接矩阵也不管顶点数量最后建一个 10 万×10 万的矩阵把内存撑爆。这就是没做设计。1.2 为什么邻接矩阵和邻接表能成为主流方案市面上图存储方案不少有邻接矩阵、邻接表、十字链表、邻接多重表等等但绝大多数教学和工程场景你只需要掌握前两个剩下的是针对特殊需求的优化版。邻接矩阵的思路非常直观开一个 N×N 的二维数组matrix[i][j] 为 1 表示顶点 i 到 j 有一条边为 0 表示没有。对于带权图直接把矩阵里的值替换成权重用无穷大表示“不可达”。这种结构最大的优势是查询一条边是否存在是 O(1) 时间复杂度写起来也顺手Python 里一个双层列表就搞定。邻接表则换了一种思路每个顶点对应一个链表Python里常用 list链表里存的是与它相邻的顶点。整体看起来像一个数组加链表的组合。它的优势是空间效率高对于稀疏图边远少于顶点平方存储开销小得多同时遍历某个顶点的所有邻居时复杂度是 O(度)不用像邻接矩阵那样扫一整行 N 个格子。至于怎么选我自己总结的经验就三条顶点少几百以内且要频繁判断两点是否连通用邻接矩阵顶点多、边稀疏或者需要频繁遍历邻居用邻接表如果是考试或作业写着练手选你最有把握的那一个但心里要清楚另一个的缺陷在哪。2. 核心细节解析与实操要点2.1 邻接矩阵构建中的维度、对称性与编码细节邻接矩阵虽然简单但细节里全是坑。先说维度。假设图里有 V 个顶点你需要一个 V×V 的矩阵。在 Python 里最经典的错误是用[[0] * V] * V来初始化。这种行为会造成每行引用同一个列表对象表面看是二维数组实际改一个元素整列都跟着变。正确做法是[[0]*V for _ in range(V)]列表推导式生成独立行。接下来是顶点编号问题。现实中顶点可能是字符串比如城市名、用户ID你要先做一次映射把字符串转成 0 到 V-1 的整数索引。我见过不少同学忘了这步直接拿字符串当下标程序瞬间报错。构建前先建立一个字典例如{北京:0, 上海:1}后续所有操作都基于数字下标这既能提速也方便和邻接表统一。对于无向图矩阵是对称的。也就是说添加一条边 u-v 时你得同时设置matrix[u][v]1和matrix[v][u]1。漏掉任意一边都算图没建全。对于有向图则只设前者。带权图同理给对应位置赋权重无穷大一般用float(inf)或一个足够大的数比如 99999不推荐用负数不然后面的最短路径算法会直接懵圈。还有一个小细节自环和重边。自环就是顶点连自己矩阵里的对角线元素。多数算法允许自环但对角线设成 1 还是 0 取决于问题语义。重边在简单图里一般忽略矩阵天然只记录一条边。如果你用的是邻接表就需要注意重复添加的问题。2.2 邻接表构建中的链表结构与动态扩容技巧邻接表的 Python 实现我推荐用“列表套列表”或者“列表套字典”。列表套列表就是adj [[] for _ in range(V)]然后adj[u].append(v)。如果你想同时存权重可以改成adj[u].append((v, w))或者直接用字典套列表adj {i:[] for i in range(V)}。这里有一个很多人忽略的点邻接表的顶点顺序默认是“插入顺序”而你后续做深度优先搜索DFS时遍历邻居的先后会直接影响搜索路径。如果题目要求按编号升序访问邻居你必须在插入后排序或者在构建时就按需插入。比如adj[u].append(v)之后调用adj[u].sort()别小看这步很多路径题的结果对顺序敏感。另一个问题是“无向图双向插入”。用邻接表时添加无向边 u-v 必须执行两次 appendadj[u].append(v)和adj[v].append(u)。漏掉一次图就变成了有向图你在 DFS 时就会漏顶点。我在调试学生的代码时超过一半的“漏点”问题都出在这一行上。空间优化方面如果你预先知道边的数量可以用reserve思想提前分配好容量。不过 Python 里的 list 自动扩容已经很高效平时写不用太纠结。真正要留意的是极限值当 V 有 10 万级别时邻接表的创建要避免使用{i:[] for i in range(V)}这种纯 Python 循环可以改用defaultdict(list)语义上更安全同时初始化速度也更快。3. 实操过程与核心环节实现3.1 从零开始构建一个无向无权图完整代码与分步说明我直接给出一套我自己常用的构建模板。假设输入是顶点列表[A,B,C,D]边列表[(A,B),(B,C),(C,D),(D,A)]。第一步建映射第二步建邻接表第三步顺手建个邻接矩阵做交叉验证。vertices [A, B, C, D] edges [(A, B), (B, C), (C, D), (D, A)] # 1. 顶点映射 index {v: i for i, v in enumerate(vertices)} n len(vertices) # 2. 邻接矩阵初始化 matrix [[0] * n for _ in range(n)] # 3. 邻接表初始化 adj [[] for _ in range(n)] # 4. 构建 for u, v in edges: i, j index[u], index[v] matrix[i][j] 1 matrix[j][i] 1 # 无向图对称 adj[i].append(j) adj[j].append(i) print(邻接矩阵:) for row in matrix: print(row) print(邻接表:) for i in range(n): print(f{vertices[i]}: {[vertices[j] for j in adj[i]]})运行结果非常直观矩阵是 4×4 的对称 0/1 数组邻接表则每个顶点都能列出自己的邻居。这套代码里映射表的构建是核心——没有 index 字典后面边列表没法快速定位。如果你换一种输入方式比如直接给定的是整数顶点编号可以省掉映射环节但实际业务里极少有这种好事所以映射一定要写好。带权图也很容易扩展把矩阵的1改成权重把邻接表的整数邻居改成元组例如(v, weight)。后面跑 Dijkstra 的时候邻接表遍历邻居取权重就非常顺手。这里提醒一下无向带权图一样要添加两次权重相同别写错。3.2 深度优先与广度优先遍历构建之后的第一件事图构建好了下一步通常是验证连通性。遍历算法就是最直接的验证器。我提供两个标准实现都用上面构建出来的邻接表。def dfs(adj, start, visited): visited[start] True print(start, end ) for neighbor in adj[start]: if not visited[neighbor]: dfs(adj, neighbor, visited) def bfs(adj, start): from collections import deque visited [False] * len(adj) q deque([start]) visited[start] True while q: node q.popleft() print(node, end ) for neighbor in adj[node]: if not visited[neighbor]: visited[neighbor] True q.append(neighbor)DFS 用递归虽然写起来简洁但顶点多时容易栈溢出。我在实战里更推荐显式栈版本用 list 模拟。BFS 用标准库的 deque时间复杂度 O(VE)空间也稳定。遍历顺序跟邻接表存储顺序强相关所以刚刚强调的“排序”在这一步就体现出来了想要稳定的结果最好维护一个有序邻居表。另外提一个容易忽略的测试技巧构建完图你可以随机挑一个起点跑 BFS然后用visited数组看看是否所有顶点都被访问到。如果有没有访问到的要么是非连通图要么是你的双向边漏加了一条。这个测试比肉眼检查矩阵快得多。4. 常见问题与排查技巧实录4.1 构建过程中最常出现的四类错误我统计过自己带实验课时遇到的大部分问题集中在四个地方。第一是数组初始化错误也就是刚才说的[[0]*n]*n导致共享引用。这个错误很隐蔽因为打印出来看是正常的只有当你赋值matrix[0][1]1时会发现matrix[1][1]也跟着变成了 1直接怀疑人生。排查方法很简单打印每个子列表的id看是否相同。第二是映射遗漏。顶点列表里有多个相同名字或者输入边列表里出现了顶点列表之外的顶点导致KeyError。解决方法是先做一个集合去重校验assert set(edges).issubset(set(vertices))但注意 edge 里每个元素可能是元组得展开判断。第三是无向图只加一边。这个错误在邻接表里表现得尤其明显A 能访问 BB 访问不到 A。你用 BFS 遍历时会发现图变成了“单向流动”的结构。简单验证方式是检查矩阵是否对称或者对每条边都执行assert v in adj[u] and u in adj[v]。第四是索引越界。顶点编号习惯从头开始用 1 的话矩阵就要开(n1)×(n1)用 0 下标则一切正常。很多刷题的代码默认顶点从 0 开始但实际场景偏偏从 1 开始。我的建议是无论题目怎么给统一内部转换成 0 基索引外部展示时再加1。4.2 性能调优与扩容经验当图不再“小而美”如果你只是做课程实验前面的代码已经够用。但一旦图规模上升到万级、十万级顶点你就得考虑更优的构建方式。邻接表里用 Python list 存邻居append 摊还时间复杂度是 O(1)可以接受。但如果你频繁做“判断两点是否相邻”的操作邻接表就要遍历列表那就不合算了。这时可以考虑在邻接表内部用 set 来存邻居查询复杂度降到 O(1)构建速度稍慢但整体更稳。邻接矩阵也有优化空间。稀疏图里矩阵全是 0你当然不想存一个巨大表格。如果你的内存很紧张可以考虑用一行位的字符串或者压缩数组来表示矩阵但代码复杂度会直线上升。课程设计里不建议这么折腾明白原理就行。我还想分享一个工程经验构建大图时尽量别反复调用 append 单个节点。可以先收集边到一个列表然后用批量方式构建。比如用for u, v in edges从文件读取时一次性使用adj[u].append(v)这个操作在 Python 里已经很快但如果你卡在性能上可以把所有边先按起点排序再统一构造链表结构。有点像是把杂乱的输入整理成索引数组这个思路在 C/C 里特别常见因为手动管理内存省了很多空节点分配。说实话图的构建写起来不难但“构建得好”需要你理解存储结构的本质。邻接矩阵胜在速度和直观邻接表胜在空间和遍历效率。你如果能把两种都写熟练再去看那些复杂的图算法就会觉得底层非常扎实。我个人在实际操作里最常用的其实是“邻接表 字典映射”的组合既方便调试又能应对大部分场景。最后分享一个小技巧写完构建代码后不要急着写算法先用小规模图比如 4 个顶点画一遍手推的邻接表和矩阵跟程序输出对一下。这个习惯帮我省下过太多排错时间。等图结构确认没问题再往上叠加拓扑排序、最短路径那些心里就特别有底。
