前端工程中的图结构：邻接表封装与BFS/DFS实战

1. 图结构在前端工程中的真实定位

很多前端同学觉得图结构是算法竞赛或者后端服务才用得上的东西，日常写业务页面根本碰不到。我一开始也这么想，直到遇到几个实际场景才改变看法：依赖关系分析、菜单树权限校验、组件引用拓扑排序、社交关系链路推荐、路由跳转路径规划，这些本质上都是图问题。区别只在于，树是图的特例，而图能表达“多对多”和“环路”这类树搞不定的关系。

图结构封装的核心价值在于把“点”和“边”的增删查改、遍历策略、路径记录统一收口到一个类里，业务层只关心“我要从A找到B”或者“我要按某种顺序处理所有节点”，不用每次手写一堆散落的邻接矩阵或者对象映射。邻接表是我个人最推荐的实现方式，原因很直接：大部分真实场景的图是稀疏图，用二维数组存邻接矩阵会浪费大量空间，而邻接表只存实际存在的边，内存占用和遍历效率都更友好。

这篇文章面向的是已经会写JavaScript、但对图结构还停留在“听说过BFS和DFS”阶段的开发者。我会从零封装一个基于邻接表的图类，把广度优先搜索和深度优先搜索的迭代与递归版本都实现一遍，并且解释每个设计决策背后的理由。读完之后，你可以直接把这个类拿去用在权限校验、依赖分析、路径查找等场景里，也可以根据业务需要扩展加权边、有向图等变体。

2. 邻接表方案的整体设计与选型考量

2.1 为什么不用邻接矩阵

邻接矩阵的本质是一个二维布尔数组，matrix[i][j]表示节点i到节点j是否有边。它的优点是查询两个节点是否相邻的时间复杂度是O(1)，但缺点同样明显：空间复杂度固定为O(V²)，V是节点数量。假设你有1000个节点，矩阵就要占100万个格子，哪怕实际只有几条边。而邻接表的空间复杂度是O(V+E)，E是边的数量，稀疏图下优势巨大。

另一个关键点是遍历邻居的效率。邻接矩阵要找出某个节点的所有邻居，必须扫描整行，耗时O(V)；邻接表直接读取该节点对应的邻居列表，耗时O(degree)，degree是该节点的度数。在BFS和DFS中，核心操作就是“获取当前节点的所有邻居”，所以邻接表在遍历场景下天然更快。

我实测过一个社交关系模拟数据：5000个用户，平均每人关注20个人，总边数约10万。用邻接矩阵初始化时内存直接飙到几百MB，浏览器标签页差点崩掉；换成邻接表后内存稳定在几十MB，BFS遍历一圈的耗时也从秒级降到毫秒级。这个差距在真实项目里是致命的。

2.2 邻接表的数据结构选择

邻接表可以用对象、Map或者数组来实现。我最终选择用Map作为外层容器，用Set作为邻居集合，理由有三条。

第一，Map的键可以是任意类型，不限于字符串或数字。业务里节点ID可能是数字、字符串、甚至对象引用，Map都能hold住，而普通对象会把数字键悄悄转成字符串，埋下隐患。第二，Map的has、get、set、delete操作都是O(1)平均复杂度，性能稳定。第三，Set自动去重，避免重复添加同一条边导致邻居列表膨胀，省去了手动查重的代码。

有些同学喜欢用数组存邻居，觉得遍历快。数组确实在遍历时缓存友好，但删除边的时候要遍历查找再splice，复杂度O(degree)，而且容易漏掉重复项。Set的删除是O(1)，代码也更干净。如果后续需要按顺序遍历邻居，可以在获取邻居列表时临时转成数组排序，灵活性更高。

2.3 有向图与无向图的统一处理

有向图和无向图的区别只在于加边时是否双向添加。我的设计是在构造函数里接收一个directed参数，默认false表示无向图。addEdge方法内部根据这个标志决定是否反向再连一次。这样一套代码同时支持两种图，不用维护两个类。

这里有个容易踩的坑：无向图删除边时也要双向删除，否则会残留“半边”，导致遍历时出现幽灵路径。我在早期版本里就犯过这个错，调试了半天才发现是删边只删了一个方向。所以removeEdge方法同样要根据directed标志做对称处理。

3. 图类核心方法的逐行拆解

3.1 构造函数与基础属性

class Graph { constructor(directed = false) { this.adjacencyList = new Map(); this.directed = directed; } }

adjacencyList是核心存储，键是节点，值是该节点的邻居Set。directed记录图的方向性，影响加边和删边的行为。构造函数里不预设任何节点，所有节点通过addVertex或addEdge动态加入，这样更灵活。

我特意没有在构造函数里接受初始节点数组，因为业务里图的构建往往是增量的，比如从接口分批拉取数据。如果确实需要批量初始化，可以额外写一个静态方法或者工具函数，不必塞进构造函数增加复杂度。

3.2 添加节点与添加边

addVertex(vertex) { if (!this.adjacencyList.has(vertex)) { this.adjacencyList.set(vertex, new Set()); } return this; } addEdge(from, to) { this.addVertex(from); this.addVertex(to); this.adjacencyList.get(from).add(to); if (!this.directed) { this.adjacencyList.get(to).add(from); } return this; }

addVertex做了幂等处理，重复添加同一个节点不会覆盖已有的邻居集合。这一点很重要，否则先加边再加节点会把边清空。addEdge先确保两个端点都存在，再建立连接。返回this是为了支持链式调用，写起来更顺手。

注意：如果业务里节点ID是对象，Set的去重是基于引用比较的，两个内容相同但引用不同的对象会被当成不同节点。这种情况下建议用唯一ID字符串作为节点标识，把对象数据存在外部映射里。

3.3 删除节点与删除边

removeVertex(vertex) { if (!this.adjacencyList.has(vertex)) return this; this.adjacencyList.delete(vertex); for (const neighbors of this.adjacencyList.values()) { neighbors.delete(vertex); } return this; } removeEdge(from, to) { if (this.adjacencyList.has(from)) { this.adjacencyList.get(from).delete(to); } if (!this.directed && this.adjacencyList.has(to)) { this.adjacencyList.get(to).delete(from); } return this; }

删除节点比删除边麻烦，因为要清理所有其他节点对该节点的引用。我选择遍历整个邻接表，逐个删除。这个操作的时间复杂度是O(V+E)，在频繁删除的场景下可能成为瓶颈。如果业务需要高频删除，可以考虑维护一个反向索引，但大多数场景下这个开销可以接受。

删除边时先判断节点是否存在，避免对undefined调用delete报错。无向图要双向删除，有向图只删一个方向。这里我用了has判断而不是直接get，因为get返回undefined时再调delete会抛异常。

3.4 查询方法与辅助工具

hasVertex(vertex) { return this.adjacencyList.has(vertex); } hasEdge(from, to) { return this.adjacencyList.has(from) && this.adjacencyList.get(from).has(to); } getNeighbors(vertex) { return this.adjacencyList.has(vertex) ? Array.from(this.adjacencyList.get(vertex)) : []; } getVertices() { return Array.from(this.adjacencyList.keys()); } get vertexCount() { return this.adjacencyList.size; } get edgeCount() { let count = 0; for (const neighbors of this.adjacencyList.values()) { count += neighbors.size; } return this.directed ? count : count / 2; }

getNeighbors返回数组而不是Set，是为了让调用方可以自由排序或索引，同时避免外部直接修改内部Set。每次调用都会创建新数组，有一定开销，但在BFS/DFS里这是必要的隔离。如果追求极致性能，可以返回Set的迭代器，但那样调用方处理起来更麻烦，我倾向于可读性优先。

edgeCount对无向图要除以2，因为每条边被存了两次。有向图则直接累加。这个getter在调试和统计时很有用。

4. 广度优先搜索的实现与场景适配

4.1 BFS的核心逻辑与队列选择

BFS的本质是“层层推进”：从起点开始，先访问所有距离为1的邻居，再访问距离为2的邻居，依此类推。实现上依赖一个队列，每次从队头取出节点，把它的未访问邻居加入队尾。

队列用数组加shift方法最简单，但shift的时间复杂度是O(n)，在大图上会成为性能瓶颈。我实测过10万节点的图，用shift的BFS耗时是用双指针队列的3倍以上。所以生产代码里我推荐用“头指针+数组”的方式模拟队列，或者用链表实现真正的O(1)出队。

bfs(start, callback) { if (!this.adjacencyList.has(start)) return []; const visited = new Set(); const queue = [start]; let head = 0; const order = []; visited.add(start); while (head < queue.length) { const vertex = queue[head++]; order.push(vertex); if (callback) callback(vertex); for (const neighbor of this.adjacencyList.get(vertex)) { if (!visited.has(neighbor)) { visited.add(neighbor); queue.push(neighbor); } } } return order; }

visited集合在入队时就标记，而不是出队时标记。这个细节很关键：如果出队时才标记，同一个节点可能被多个邻居重复加入队列，导致队列膨胀甚至死循环。入队即标记能保证每个节点最多入队一次。

4.2 BFS记录路径与距离

单纯遍历节点往往不够，业务里更常见的是“找到从A到B的最短路径”或者“每个节点距离起点多少步”。BFS天然适合做这件事，因为它是按距离递增的顺序访问节点的。

bfsShortestPath(start, end) { if (!this.adjacencyList.has(start) || !this.adjacencyList.has(end)) { return null; } if (start === end) return [start]; const visited = new Set([start]); const queue = [start]; let head = 0; const parent = new Map(); while (head < queue.length) { const vertex = queue[head++]; for (const neighbor of this.adjacencyList.get(vertex)) { if (visited.has(neighbor)) continue; visited.add(neighbor); parent.set(neighbor, vertex); if (neighbor === end) { return this.buildPath(parent, start, end); } queue.push(neighbor); } } return null; } buildPath(parent, start, end) { const path = [end]; let current = end; while (current !== start) { current = parent.get(current); path.unshift(current); } return path; }

parent映射记录每个节点的前驱，找到终点后沿着parent回溯就能得到路径。unshift在小路径上没问题，如果路径很长可以用push再reverse，性能更好。

实操心得：BFS找最短路径只适用于无权图。如果边有权重，BFS找到的不一定是最短路径，需要用Dijkstra或A*算法。这一点在业务里很容易搞混，我曾经在一个带权重的路由场景里用BFS，结果路径长度对不上，排查半天才发现是算法选错了。

4.3 BFS的典型应用场景

BFS最擅长的场景是“最短”和“层级”相关的问题。比如社交网络里的“几度人脉”，从当前用户出发，BFS第一层是直接好友，第二层是好友的好友，找到目标用户时的层数就是度数。再比如迷宫寻路，每个格子是节点，相邻格子有边，BFS能保证找到最短步数的路径。

还有一个容易被忽略的场景是“连通分量检测”。对图里每个未访问节点跑一次BFS，每次BFS覆盖到的所有节点构成一个连通分量。这个逻辑在权限组分析、网络分区检测里很实用。

5. 深度优先搜索的实现与变体

5.1 递归版DFS的简洁与局限

递归版DFS代码最短，逻辑最直观：访问当前节点，标记已访问，然后递归访问所有未访问的邻居。

dfsRecursive(start, callback) { const visited = new Set(); const order = []; const traverse = (vertex) => { visited.add(vertex); order.push(vertex); if (callback) callback(vertex); for (const neighbor of this.adjacencyList.get(vertex)) { if (!visited.has(neighbor)) { traverse(neighbor); } } }; if (this.adjacencyList.has(start)) { traverse(start); } return order; }

递归的局限在于调用栈深度。JavaScript引擎对递归深度有限制，不同环境不一样，但通常在几千到一万层左右。如果图是一条长链，比如1万个节点依次相连，递归DFS会直接爆栈。我实测过在某个浏览器环境下，递归深度超过约1万就抛“Maximum call stack size exceeded”。

所以递归版适合节点数量可控、图比较“扁”的场景。如果图的深度不确定，或者节点数可能上万，必须用迭代版。

5.2 迭代版DFS与栈的使用

迭代版DFS用显式栈模拟递归，避免了调用栈溢出。但这里有个细节：入栈顺序会影响遍历顺序。如果按邻居的自然顺序入栈，出栈时顺序会反过来。如果想要和递归版一致的遍历顺序，需要逆序入栈。

dfsIterative(start, callback) { if (!this.adjacencyList.has(start)) return []; const visited = new Set(); const stack = [start]; const order = []; while (stack.length > 0) { const vertex = stack.pop(); if (visited.has(vertex)) continue; visited.add(vertex); order.push(vertex); if (callback) callback(vertex); const neighbors = Array.from(this.adjacencyList.get(vertex)); for (let i = neighbors.length - 1; i >= 0; i--) { if (!visited.has(neighbors[i])) { stack.push(neighbors[i]); } } } return order; }

注意这里的visited判断在出栈时进行，而不是入栈时。因为同一个节点可能被多次入栈（不同邻居都指向它），出栈时判断可以跳过重复处理。这和BFS的入队即标记不同，原因是DFS的栈是后进先出，入栈时标记会导致某些路径被提前截断。

注意：迭代版DFS的遍历顺序和递归版不一定完全相同，取决于邻居的入栈顺序。如果业务对遍历顺序有严格要求，需要仔细控制入栈顺序，或者干脆用递归版（在深度可控的前提下）。

5.3 DFS在环检测与拓扑排序中的应用

DFS有一个BFS不具备的能力：检测环。在遍历过程中，如果遇到一个已经在当前递归路径上的节点，说明存在环。实现上需要维护两个集合：visited记录所有访问过的节点，recursionStack记录当前递归路径上的节点。

hasCycle() { const visited = new Set(); const recursionStack = new Set(); const detect = (vertex) => { visited.add(vertex); recursionStack.add(vertex); for (const neighbor of this.adjacencyList.get(vertex)) { if (!visited.has(neighbor)) { if (detect(neighbor)) return true; } else if (recursionStack.has(neighbor)) { return true; } } recursionStack.delete(vertex); return false; }; for (const vertex of this.adjacencyList.keys()) { if (!visited.has(vertex)) { if (detect(vertex)) return true; } } return false; }

这个逻辑在依赖分析里非常有用。比如构建工具需要判断模块之间是否存在循环依赖，如果有环就无法确定构建顺序，必须报错提示用户。拓扑排序也是基于DFS的后序遍历实现的：一个节点所有邻居都处理完后，把它加入结果数组的前端，最终得到的就是拓扑序。

6. 性能对比与实测数据

6.1 BFS与DFS的复杂度分析

三者时间复杂度相同，因为每个节点和每条边都只处理常数次。空间上BFS的队列最多存一层节点，DFS的栈最多存一条路径，最坏情况都是O(V)。递归版额外占用调用栈空间，深度大时有爆栈风险。

6.2 实测数据与选型建议

我在本地用Node.js跑了一组对比测试，图的结构是随机生成的稀疏图，节点数从1千到10万，边数约为节点数的3倍。结果如下：

小规模下三者差距不大，递归甚至略快，因为函数调用优化得好。但到10万节点时递归直接爆栈，迭代版稳定在200ms左右。BFS和DFS迭代版性能接近，选哪个取决于业务需求：要最短路径用BFS，要环检测或拓扑排序用DFS。

实操心得：如果图特别大（百万级节点），可以考虑用TypedArray替代Set和Map来存邻接关系，内存和速度都会有明显提升。但代码复杂度会上升，除非确实遇到性能瓶颈，否则没必要过早优化。

7. 常见问题与排查技巧实录

7.1 遍历结果不完整或死循环

这是最常见的问题，根源通常是visited标记的时机不对。BFS必须在入队时标记，DFS迭代版在出栈时标记，DFS递归版在进入函数时标记。如果标记时机错了，要么重复访问导致死循环，要么提前截断导致漏访问。

排查方法：在遍历过程中打印每次入队/出栈的节点，观察是否有重复。如果同一个节点出现多次，就是标记时机问题。另一个检查点是visited集合是否在每次遍历前重新初始化，如果复用了上一次的集合，第二次遍历会直接跳过所有节点。

7.2 无向图边数统计翻倍

前面提过，无向图每条边存两次，edgeCount要除以2。如果发现边数比预期多一倍，先检查这个。另外，如果用了addEdge多次添加同一条边，Set会自动去重，不会重复计数，这一点比数组实现更省心。

7.3 节点ID类型不一致导致查不到

JavaScript里1和'1'是不同的键。如果从接口拿到的ID是字符串，手动测试时用的是数字，就会出现“明明加了节点却查不到”的情况。建议在图的入口处统一做类型转换，比如全部转成字符串，或者在文档里明确约定节点ID类型。

7.4 递归DFS爆栈的应急处理

如果线上环境突然报栈溢出，最快的修复是把递归改成迭代。如果时间紧迫，也可以临时增大栈大小（Node.js可以用--stack-size参数），但这只是缓兵之计，根本方案还是迭代实现。我在一个紧急修复里用过这个参数，把栈从默认的984KB调到4096KB，暂时扛住了，但第二天还是老老实实改成了迭代版。

7.5 性能问题的排查思路

图算法性能问题通常出在三个地方：队列/栈的实现、邻居列表的遍历、visited的查询。队列用shift是经典性能杀手，换成头指针立竿见影。邻居列表如果每次遍历都Array.from转换，在大图上开销可观，可以考虑缓存或者直接用Set的迭代器。visited用Set查询是O(1)，但如果节点是复杂对象，哈希开销会上升，此时用唯一ID字符串更划算。

8. 可扩展方向与工程化建议

8.1 加权边与最短路径扩展

当前实现只支持无权图。如果业务需要处理带权重的边，可以把邻居Set改成Map，值是权重。BFS要换成Dijkstra算法，用优先队列替代普通队列。优先队列可以用二叉堆实现，JavaScript没有内置堆，需要自己写一个或者用现成的库。这个扩展在路由规划、成本优化场景里很常见。

8.2 序列化与持久化

图结构如果需要存到数据库或者通过网络传输，需要序列化。Map和Set默认不能被JSON.stringify正确处理，要手动转成数组或对象。我通常写一对toJSON和fromJSON方法，把邻接表转成{ vertices: [...], edges: [...] }的格式，反序列化时重建。这样存储体积小，也方便版本迁移。

8.3 与业务代码的解耦

图类应该保持纯粹，不掺杂业务逻辑。业务层通过回调或者继承来扩展。比如权限校验场景，可以在遍历时传入一个shouldVisit回调，决定是否继续深入某个分支。这样图类不用改，业务逻辑灵活组合。

我在实际项目里把这个图类用在了三个地方：组件依赖分析、菜单权限过滤、接口调用链追踪。每次都是直接引入，最多加个回调，没有改过图类本身的代码。这种“一次封装，多处复用”的体验，正是抽象带来的价值。后续如果遇到需要加权或者有向图的场景，我也会优先在这个类上扩展，而不是重新造轮子。