很多学数据结构的人学到图这一章的时候都有过同一个困惑书本上用圆圈和箭头画得明明白白的图真到自己动手写代码却不知道该怎么把它落到程序里。我带新人做项目的时候也经常看到有人卡在第一步——“图的构建”听起来是个基础操作可真让你在半小时里用一门语言把它写出来并且写对、写稳、能应对后续的遍历和算法并没有想象中那么轻松。我写这篇就是想把这件“基础但不简单”的事彻底讲透图到底是什么为什么会有邻接矩阵和邻接表这两种主流存储方式不同语言下怎么选怎么实现以及我在实际工程里踩过哪些坑。不管你是正在准备数据结构期末考的学生准备实验报告写到头秃的课设党还是刷题备战面试的求职者或者是需要在业务代码里维护一张关系网的开发这篇文章应该都能给你一些直接的参考。1. 图的构建动手之前先把图这种结构“翻译”成人话1.1 图的两个基本零件顶点与边图论里一张图就是一个二元组 G (V, E)V 是所有顶点的集合E 是所有边的集合。顶点在代码里通常就是整数编号或者字符串名字边则是一条连接两个顶点的关系记录。很多人觉得图难不是难在概念而是难在“关系”这个词太抽象。对比一下线性表和树数组和链表天然有先后顺序树有父亲和孩子的层级你写代码时顺着结构走就行。图没有天然的起点也没有天然的“上下级”任何两个顶点之间都可能存在关系这种自由恰恰是它强大的来源也是存储它时需要额外设计的原因。用交通图来类比最容易理解地铁站是顶点站与站之间的铁轨是边你从换乘站出发能去哪些站取决于这张图上哪些顶点之间有边相连。你不需要理解铁轨怎么铺只需要知道从 A 站能不能到 B 站——这就是图存在的意义把“谁和谁有关”这件事登记下来并且方便后续查询。1.2 动手前先明确三件事方向、权重、规模我开始写图之前一定会先问自己三个问题这三个问题的答案直接决定我选什么存储结构、怎么设计数据结构的接口。如果这个问题没想清楚就打开编辑器写代码后面大概率要返工。第一边有没有方向。有方向的图叫有向图边写作从 u 指向 v没方向的叫无向图边只表示 u 和 v 之间有关系方向不重要。微博的关注关系是有向图——你关注了大V大V不一定关注你微信的好友关系是无向图互为好友才叫好友。第二边有没有权重。地图导航里的道路有路程、有耗时这种关系带数值叫加权图纯结构关系叫无权图。你做最短路径算法时没权重和有权重的处理完全是两套逻辑。第三图的规模到底多大。是几百个顶点还是几万个顶点边是稀疏还是稠密这决定了你选邻接矩阵还是邻接表。很多人不先把规模问清楚就开写结果小数据没问题一上规模就内存爆掉。1.3 构建图前先算两笔账点数和边数写代码前先把 V 和 E 的数量级估算出来顺便算一下平均度数。平均度数的公式很简单无向图是 2E / V有向图是 E / V。理解这个值有什么意义它直接告诉你每个顶点平均要挂多少个邻居进而决定你的存储结构。举一个实际例子一个社交网络有 1 万个用户平均每人关注 100 个其他用户那么 V 10000E ≈ 10000 × 100 100 万条边。这种图的边数远小于 n²是典型稀疏图。如果你用邻接矩阵存10000 × 10000 1 亿个格子就算每个格子只存一个 int也要 400MB 内存直接不可用。反过来一个班级 50 人互相都认识那么 E 50 × 49 / 2 1225 条边已经逼近完全图的上限属于稠密图。这时邻接矩阵反而更合适不但实现简单还能获得 O(1) 的查边效率。提示选存储结构前先算规模不是数学题是为了避免内存爆炸。这个习惯能帮你省掉后面大量调试时间。2. 两种主流存储方案邻接矩阵与邻接表的原理拆解图的核心操作其实就三件事加边、查边、遍历某个顶点的所有邻居。存储结构的设计目标无非是让这三件事在空间和时间上取得最佳平衡。下面把邻接矩阵和邻接表彻底拆开看。2.1 邻接矩阵一张 n 行 n 列的“查表”邻接矩阵用一个二维数组来存图。graph[i][j] 为 1或者权重值表示 i 到 j 有边否则为 0或者无穷大。无向图的矩阵必然沿着对角线对称因为 i 和 j 有边j 和 i 也一定有边。这个特性在后面做某些算法时可以利用比如只需要遍历矩阵上半部分能省一半时间。这个方案的优点非常直观。第一代码极简初始化一个二维数组就完事第二查任意两点之间有没有边时间复杂度是 O(1)直接数组下标取值第三实现深度优先和广度优先遍历时不需要追指针代码逻辑非常清晰。我自己在给新手讲图遍历时就喜欢先用邻接矩阵作为入门版本因为它把“遍历”这件事的流程暴露得一清二楚不会被存储细节干扰。缺点也很致命空间固定是 O(n²)。n 稍微大一点内存就吃紧。1 万顶点、每个元素 4 字节就是 400MB还没算其他开销。所以邻接矩阵的适用面其实很窄稠密图、顶点数量小的题目、以及需要频繁判断任意两点关系的算法场景。2.2 邻接表把边存在“邻居名单”里邻接表的思路和矩阵完全相反不给所有可能的关系都预留位置只给实际存在的边分配空间。每个顶点维护一条链表或者其他动态集合链表里存的是所有和它直接相连的顶点编号。同样 1 万个用户、100 万条关注关系用邻接表只需要存 100 万个链表节点内存量级和矩阵完全不同。邻接表的缺点也显而易见查边变慢了。想知道 i 和 j 是否有边得遍历 i 的邻居链表逐个比对时间复杂度是 O(degree(i))。在稀疏图里这个代价可以接受因为平均度数很小但如果一个顶点有几千个邻居查一次边就得扫几千个节点。另外链表实现如果每个节点都单独 malloc指针本身也会占用额外内存而且节点在内存里不连续遍历时 CPU 缓存命中率低。这也是为什么 Java 里我更倾向用 ArrayList 而不是 LinkedList 来模拟邻接表——数组的连续内存访问速度更快这个细节在百万顶点级别的大图上尤其明显。2.3 复杂度对比与选型原则直接放一张对比表这也是面试里经常被考到的点维度邻接矩阵邻接表空间复杂度O(n²)O(n m)判断两顶点是否相邻O(1)O(degree(u))遍历某个顶点的邻接点O(n)O(degree(u))适合场景稠密图、顶点少稀疏图、顶点多、需要遍历邻居实现难度低中等选型原则用一句话总结边数 m 接近 n² 时用矩阵m 远小于 n² 时用邻接表。实际工程里绝大部分图都是稀疏图所以邻接表是默认选择。只有做 Floyd-Warshall 这类需要频繁查任意两点关系的算法时我才会优先考虑矩阵。另外还有一个实用判断法如果你在思考“这个题里图算稀疏还是稠密”八成是稀疏图直接用邻接表就行别纠结。3. 三语言实现邻接表从零写起来光讲原理不够直接给三套代码。我分别用 C、Java、Python 实现了同一个无向无权图的构建然后在最后给出验证思路。三种语言都写一遍你会发现存储结构选型的本质从来没变变的只是语法和工程细节。3.1 C 语言版指针构建邻接表顺便复习内存管理C 语言版最能体现邻接表的本质——每个顶点后面带着一条边链表。结构体定义如下。#define MAX_VERTEX_NUM 100 typedef struct EdgeNode { int adjvex; // 邻接点的编号 struct EdgeNode *next; // 指向下一条边 } EdgeNode; typedef struct VertexNode { int data; // 顶点数据比如编号 EdgeNode *firstEdge; // 第一条边的指针 } VertexNode; typedef struct { VertexNode vertices[MAX_VERTEX_NUM]; int vertexNum, edgeNum; } Graph;插入一条无向边时要同时更新两个顶点的链表。void addEdge(Graph *g, int u, int v) { // 头插法把新边节点插入 u 的链表头部 EdgeNode *nodeU (EdgeNode*)malloc(sizeof(EdgeNode)); nodeU-adjvex v; nodeU-next g-vertices[u].firstEdge; g-vertices[u].firstEdge nodeU; // 无向图还要往 v 的链表中插入 u EdgeNode *nodeV (EdgeNode*)malloc(sizeof(EdgeNode)); nodeV-adjvex u; nodeV-next g-vertices[v].firstEdge; g-vertices[v].firstEdge nodeV; g-edgeNum; }这里有个细节值得注意头插法会让同一顶点的邻接链表顺序和插入顺序相反遍历出来的序列是倒序。如果你希望遍历结果符合直觉可以用尾插法每次找到链表末尾再接上节点。但头插法的时间复杂度是 O(1)尾插法是 O(degree)所以在线性构建图中头插法更常用。我的判断标准是除非业务要求遍历顺序与输入一致否则都用头插法。用 C 语言还有一个事项必须提醒malloc 分配的每个边节点用完以后都要 free。我见过不少实验报告里图构建部分运行一次崩一次十有八九是内存管理问题。写一个遍历函数做验证之前先把退出前的释放逻辑写好这是个好习惯。3.2 Java 版面向对象封装接口清晰可维护在 Java 里再写裸指针就太累了。工程上我通常用 List 数组来模拟邻接表本质和指针链表一样但代码可读性高一个量级也不用手动管理内存。class Graph { private ListListInteger adj; private int vertexNum; private int edgeNum; public Graph(int n) { this.vertexNum n; adj new ArrayList(n); for (int i 0; i n; i) { adj.add(new ArrayList()); } } public void addEdge(int u, int v) { adj.get(u).add(v); adj.get(v).add(u); // 无向图 edgeNum; } public ListInteger neighbors(int v) { return adj.get(v); } }这种写法的空间和 C 语言的链表有区别ArrayList 分配的是连续数组当列表扩容时会整体搬移但均摊复杂度仍然是 O(1)。更重要的是后续写 BFS、DFS、最短路径时拿到邻居列表后直接 for 遍历非常舒服。如果你提前知道了每个顶点的度数上限可以用指定初始容量的写法来避免扩容损耗adj.add(new ArrayList(maxDegree));这个优化在小图上看不出来但在几万顶点、每个顶点上千邻居的大图上能明显减少数组复制的时间。我在做图相关的比赛题时经常这样写。3.3 Python 版字典加列表五分钟搭出原型Python 做图构建是我用过的语言里最省心的。直接用字典把顶点映射到邻居列表不需要提前声明总长度顶点还可以用任意可哈希类型比如字符串名字这对原型验证非常友好。from collections import defaultdict def build_graph(edges, directedFalse): graph defaultdict(list) for u, v in edges: graph[u].append(v) if not directed: graph[v].append(u) return graph # 用法示例 edges [(A, B), (A, C), (B, D), (C, D)] g build_graph(edges)defaultdict 的好处是访问不存在的键时会自动创建空列表省去了手动 setdefault 的啰嗦代码。但在做图算法题时要注意如果题目给的是 n 个顶点、编号 0 到 n - 1更稳妥的办法是预先初始化 n 个空列表这样即使某些顶点没有任何边也存在于图中遍历的时候不会被漏掉。n 5 graph [[] for _ in range(n)] for u, v in edges: graph[u].append(v) graph[v].append(u)两种写法各有各的应用场景业务原型阶段顶点是字符串 ID 时用 defaultdict算法竞赛或刷题时顶点是连续整数时用固定长度列表。我自己的习惯是刷题时固定用第二种因为省掉了字典哈希的开销性能更好。3.4 构建完成后怎么确认图建对了写代码最忌讳建完图就自认为正确。我每次建完图都会写一个简单的 BFS 或 DFS 来验证。比如刚才那个例子从 A 出发 BFS如果按预期访问到 A、B、C、D同时打印访问顺序和边数对不上就说明哪里出了问题。验证的核心思路是三大检查。第一顶点数对不对尤其是有没有把孤立点漏掉第二边数对不对无向图的 addEdge 如果忘了双向添加边数会少一半第三方向性对不对有向图的边有没有被错误地当成无向图处理。建议写一段代码在构建完成后断言无向图中遍历所有顶点邻居的累加次数应该等于 2 倍边数。这个小断言能在早期拦住大量低级错误。4. 从数据结构到业务语义加权图与有向图的构建细节很多初学者把图建完就以为万事大吉可一旦接入真实业务就会发现还要面对权重、方向、自环、重边这些“第二次门槛”。这些细节恰恰是工程代码和教科书代码的分水岭。4.1 权重怎么挂到边上无权图用 1 表示“有关系”加权图就要把 1 换成具体的数值。存储层面邻接表的节点从只存邻接顶点编号变成存“顶点编号 权重”的二元组。C 语言改结构体在 EdgeNode 里加一个 weight 字段Java 改成存内部类 Edge 或者 int[]Python 则用元组。用 Python 举例构建带权有向图的核心代码变化很小edges [(A, B, 3), (A, C, 5), (B, C, 2)] graph defaultdict(list) for u, v, w in edges: graph[u].append((v, w))存权重之后遍历邻接点时要顺手取出权重。这个改动看起来小但直接影响后面的算法代码Dijkstra 算法里取邻居时得拆包用两个独立列表还是元组列表你得在一开始就想好中途改结构极其痛苦。我见过一个人在建图时没想清楚Dijkstra 写了 200 行最后回头改图的存储结构改了一整个下午。图纸上的决定会一路传染到算法层。4.2 方向性有向图的“单向车道”有向图的构建在代码上只需要给每条边加一次不需要反过来再加。但实际工程里方向语义经常被忽略最典型的坑是图本身是双向的但业务上某些路径单向不通。比如模块的编译依赖、课程学习的先修关系全部是有向的构建时一旦顺手写成双向后面的拓扑排序会导出完全错误的依赖链。我的习惯是构建函数显式接收一个 directed 参数就像前面 Python 示例里写的那样。把方向的决策变成接口的一部分而不是让调用方靠自觉。这算是个很小但非常实用的设计以后别人调用你的 build_graph 时看到参数名就知道要传什么不需要翻文档。4.3 特殊图树、DAG、稠密图的构建差异并不是所有的图都长一个样。树是一类特殊的无向连通图n 个顶点恰有 n - 1 条边且没有环有向无环图DAG是所有依赖关系的基础模型。构建树时如果用邻接表本质上和普通图没有区别但你可以利用“每个节点只有一个父节点”的性质用 children 表来存这样找“谁是爸爸”要另查父指针找“孩子有哪些”反而更快。DAG 必须用有向邻接表而且后续大概率要配合拓扑排序。这里有个经验如果你在构建图时就知道它是 DAG可以用一个 indegree 数组记下每个顶点的入度。拓扑排序里这一步是前置工作建图时顺手记录可以省掉后续再扫一遍图的 O(n m) 时间。稠密图和稀疏图的构建差异前面已经说过稠密选矩阵稀疏选邻接表。无论是树还是 DAG都很少有真正稠密的所以邻接表依然是默认选择。5. 工程实战中的选型经验与排查心得写到这里原理和代码都齐了。最后分享一些我在实际项目里积累的判断和教训这些不是教科书上会写的全靠踩坑换来的。5.1 什么时候我坚决不用邻接表不要以为邻接表天下无敌。如果你做的是 Floyd-Warshall 全源最短路径需要反复判断任意两个顶点是否连通邻接矩阵 O(1) 的查边性能是邻接表无法替代的。另外在顶点数很小但边较多时邻接矩阵的代码简单程度和调试优势会凸显出来。矩阵打印出来一眼就能看出结构邻接表想快速观察全貌就费劲多了。还有一种情况是权重经常需要修改。邻接矩阵改任意一条边的权重都是 O(1)直接赋值邻接表得先找到那条边再更新就要遍历链表。在动态图场景里这个差异会被放大。5.2 边集数组常被忽略的第三选择邻接矩阵和邻接表之外还有一种是边集数组把所有边放在一个数组里每个元素记录 u、v、权重。这种结构不适合查询邻居但特别适合需要“按边排序”的算法比如 Kruskal 最小生成树算法——它只需要对边按权重排序然后一条一条处理根本不关心某个顶点的邻居是谁。typedef struct { int u, v; int weight; } Edge; Edge edges[MAX_EDGE_NUM];我用 C 语言写 Kruskal 的时候通常用边集数组加并查集整个代码比邻接表版短很多。所以别把思路限制在“非矩阵即邻接表”第三选择在很多算法题里反而是最优解。5.3 我踩过的高频坑重复边、孤立点和 0/1 编号混用第一个坑是重复边。读入数据时同一对顶点可能出现多次比如文件里有三行都写着“1 2”。如果你直接 addEdge邻接表里会存三条一模一样的边BFS 时可能出现重复访问最短路径算法更会算错。处理方式取决于业务需求要么在录入时去重要么用邻接矩阵天然去重要么在 addEdge 里先查一遍。无向图查重时要注意要同时检查 u 的邻居里有没有 v以及 v 的邻居里有没有 u只查一边会有漏网之鱼。第二个坑是顶点编号从 0 还是从 1 开始。一道题里如果数据给人看时编号是 1 到 n代码里数组下标是 0 到 n - 1忘掉转换就会出现数组越界。我自己的规矩是所有算法内部统一用 0 基下标建图时把输入编号减一并且在代码注释里写清楚。这个习惯帮我避免过无数次半夜调试。第三个坑是孤立点。邻接矩阵天然会存下孤立点但邻接表如果用 HashMap 动态建表没有预先初始化所有顶点孤立点会从图中彻底消失。处理办法就是前面强调的先确定顶点全集预先初始化 n 个空列表不要让图结构依赖“出现过关系的点才存在”。第四个坑是自环也就是顶点连接到自己的边。自环在有些算法里合法有些则不允许。建图时如果不检查打印输出时看不出问题跑算法时才会炸。建议 addEdge 里加一个 if (u v) 的处理策略至少写注释说明这里允许还是禁止。5.4 用内存和时间的双维度验证图构建性能最后分享一个我常用的压测思路构建一张 10 万个顶点、100 万条边的大图分别用邻接矩阵、数组式邻接表Java ArrayList 版、链表式邻接表C 语言版实现然后统计初始化时间和内存占用。实测结果基本符合理论分析邻接矩阵内存爆炸直接不可行数组式邻接表在遍历上的缓存局部性比链表式好性能也更稳跑 BFS 的速度差距可以达到两到三倍。所以我的工程默认选项是数组式邻接表就是 Java 里的 ListList 或者 Python 里的列表套列表。只有明确需要频繁插入删除边、且顶点数量不大时才考虑链表式。这个结论在 LeetCode 中等难度的图题目里也成立绝大多数题用数组式邻接表就够了没必要为了面子去写一个带指针的复杂结构。提示性能优化不是最终目的选型是权衡。先保证正确性和可读性再针对热点操作做优化这是我在图构建这件事上最大的经验。如果你现在正准备写一张图我建议你花五分钟先回答四个问题顶点有几个、边有几条、有没有方向、有没有权重。答案都清楚了再打开编辑器选结构半小时内就能建完一张正确、可扩展的图。我自己这几年写图相关代码的最大体会就是构建这一步看似简单但它决定了后面所有算法代码的舒服程度。图纸干净了BFS、DFS、Dijkstra、拓扑排序都会自然地顺起来。