★ FEATURED ARTICLE 1. 从零手写图结构为什么邻接表是大多数场景的首选图这种数据结构刚接触的时候容易觉得抽象但它在实际开发里出现的频率远比想象中高。社交网络里的好友关系、地图导航中的路径规划、构建工具里的模块依赖分析、甚至前端项目里组件之间的引用关系本质上都是图。标题里提到的JS实现图结构封装使用邻接表实现说的就是怎么用JavaScript把图这种结构用代码表达出来并且支持广度优先搜索和深度优先搜索两种遍历方式。先说清楚一个前提图由顶点和边组成。顶点就是一个个节点边就是节点之间的连接关系。根据边有没有方向分为有向图和无向图根据边有没有权重分为带权图和不带权图。这些概念听起来像教科书但落到代码上其实很直接。那为什么用邻接表而不是邻接矩阵这是第一个需要想明白的问题。邻接矩阵是一个二维数组matrix[i][j]表示顶点i和顶点j之间有没有边。它的优点是查询两个顶点之间是否有边的时间复杂度是O(1)非常快。但缺点也很明显如果图是稀疏的也就是边数远小于顶点数的平方那么矩阵里绝大部分空间都浪费了。假设有1000个顶点但每个顶点平均只连3条边邻接矩阵要开1000×1000100万个格子而实际有值的可能只有几千个。邻接表的思路就务实得多每个顶点维护一个列表列表里只存它真正连接到的邻居。上面那个例子邻接表总共只需要存储大约3000条记录空间利用率高出一个数量级。代价是查询顶点i和顶点j是否直接相连需要遍历i的邻居列表时间复杂度是O(degree(i))也就是i的度数。在大多数实际场景里这个代价完全可以接受。我用一个具体的对比表格来说明两种方案的取舍对比维度邻接矩阵邻接表空间复杂度O(V²)O(VE)判断两点是否相邻O(1)O(degree)遍历某点所有邻居O(V)O(degree)添加边O(1)O(1)删除边O(1)O(degree)适合场景稠密图稀疏图实际项目中遇到的图绝大多数都是稀疏图。社交网络里一个用户平均好友数也就几百但整个网络有上亿用户前端项目的模块依赖图一个模块平均依赖十几个包但整个依赖树可能有几千个节点。所以邻接表是更通用的选择。在JavaScript里实现邻接表最自然的方式是用Map或者普通对象来存储。Map的好处是键可以是任意类型不限于字符串而且有内置的size属性、has方法、delete方法操作起来比普通对象更语义化。我倾向于用Map键是顶点标识值是一个数组或Set存放邻居。class Graph { constructor(isDirected false) { this.adjacencyList new Map(); this.isDirected isDirected; } addVertex(vertex) { if (!this.adjacencyList.has(vertex)) { this.adjacencyList.set(vertex, []); } } addEdge(v1, v2) { this.addVertex(v1); this.addVertex(v2); this.adjacencyList.get(v1).push(v2); if (!this.isDirected) { this.adjacencyList.get(v2).push(v1); } } }这段代码是整个图结构的地基。isDirected参数控制图是有向还是无向无向图在添加边的时候要双向添加。addVertex做了幂等处理重复添加同一个顶点不会产生副作用这个细节在实际使用中很重要因为调用方往往不确定某个顶点是否已经存在。注意用数组存邻居列表时如果同一个顶点被重复添加边数组里会出现重复项。如果业务场景不允许重复边需要在addEdge里先做一次includes检查或者直接用Set替代数组。用Set的代价是失去了索引访问能力但换来了自动去重看具体需求取舍。到这里图的基本骨架就搭好了。但光有结构还不够真正让图活起来的是遍历算法。广度优先搜索和深度优先搜索就是两种最基础的遍历策略它们各自适用于不同的问题场景。2. 广度优先搜索像水波扩散一样逐层推进广度优先搜索的核心思想是先近后远。从起始顶点出发先访问所有距离为1的邻居再访问所有距离为2的顶点以此类推像水波一样一层一层向外扩散。这个特性决定了BFS天然适合解决最短路径类问题——在无权图中BFS第一次到达某个顶点时经过的边数就是起点到该顶点的最短距离。实现BFS需要一个队列来维护待访问的顶点顺序。JavaScript里没有内置的队列用数组配合shift()方法可以实现但shift()的时间复杂度是O(n)在顶点数量大时性能会明显下降。更好的做法是用一个数组加一个头指针来模拟队列或者自己封装一个简单的队列类。class Queue { constructor() { this.items {}; this.headIndex 0; this.tailIndex 0; } enqueue(item) { this.items[this.tailIndex] item; this.tailIndex; } dequeue() { if (this.isEmpty()) return undefined; const item this.items[this.headIndex]; delete this.items[this.headIndex]; this.headIndex; return item; } isEmpty() { return this.headIndex this.tailIndex; } get size() { return this.tailIndex - this.headIndex; } }这个队列实现用对象存储元素头尾指针分别记录出队和入队位置所有操作都是O(1)。相比数组的shift()方案在数据量大时差距非常明显。我实测过在10万个顶点的图上做BFS用shift()的版本比用指针队列的版本慢了将近两个数量级。有了队列BFS的实现就很直接了bfs(startVertex, callback) { if (!this.adjacencyList.has(startVertex)) return; const visited new Set(); const queue new Queue(); const distances new Map(); const predecessors new Map(); visited.add(startVertex); queue.enqueue(startVertex); distances.set(startVertex, 0); predecessors.set(startVertex, null); while (!queue.isEmpty()) { const current queue.dequeue(); if (callback) callback(current); const neighbors this.adjacencyList.get(current); for (const neighbor of neighbors) { if (!visited.has(neighbor)) { visited.add(neighbor); queue.enqueue(neighbor); distances.set(neighbor, distances.get(current) 1); predecessors.set(neighbor, current); } } } return { distances, predecessors }; }这段代码里有几个值得展开说的设计决策。第一visited集合在顶点入队时就标记而不是在出队时标记。这个顺序很关键。如果在出队时才标记同一个顶点可能被多次入队虽然最终结果不会错但队列里会堆积大量重复元素空间和时间都会浪费。入队即标记是BFS的标准写法。第二我额外维护了distances和predecessors两个Map。distances记录起点到每个顶点的最短距离predecessors记录每个顶点是从哪个顶点过来的。这两个信息在BFS遍历过程中顺手就能算出来不需要额外遍历。有了predecessors就能反向重建出从起点到任意顶点的最短路径getShortestPath(startVertex, endVertex) { const { predecessors } this.bfs(startVertex); if (!predecessors.has(endVertex)) return null; const path []; let current endVertex; while (current ! null) { path.unshift(current); current predecessors.get(current); } return path; }unshift在这里是O(n)操作路径长度通常不会太大所以影响有限。如果追求极致性能可以先push再reverse。BFS的时间复杂度是O(VE)每个顶点入队出队一次每条边被检查一次。空间复杂度最坏情况下是O(V)队列里可能同时存在大量顶点。在社交网络的好友推荐场景里BFS常被用来找二度人脉——从当前用户出发BFS两层就能找到所有好友的好友再根据共同好友数量排序做推荐。实操心得BFS在遍历过程中如果只需要找到目标顶点就停止可以在出队时判断current target然后提前返回。这个优化在目标顶点距离起点较近时效果显著能省掉大量无谓的遍历。但要注意只有无权图才能保证BFS第一次到达目标时就是最短路径带权图需要用Dijkstra算法。3. 深度优先搜索一条路走到黑的递归与迭代之争深度优先搜索的策略和BFS正好相反沿着一条路径尽可能深入地走走到尽头再回溯换一条分支继续。这种不撞南墙不回头的方式天然适合解决连通性判断、拓扑排序、环检测、路径枚举等问题。DFS最直观的实现方式是递归。递归的调用栈本身就充当了回溯的机制代码写起来非常简洁dfsRecursive(startVertex, callback, visited new Set()) { if (!this.adjacencyList.has(startVertex)) return; if (visited.has(startVertex)) return; visited.add(startVertex); if (callback) callback(startVertex); const neighbors this.adjacencyList.get(startVertex); for (const neighbor of neighbors) { this.dfsRecursive(neighbor, callback, visited); } }递归版本的DFS代码量少逻辑清晰但有一个致命问题调用栈深度受限于JavaScript引擎的限制。不同引擎的栈深度上限不同通常在几千到一万多层左右。如果图的深度超过这个限制就会抛出Maximum call stack size exceeded错误。我在一个模拟的依赖分析场景里就踩过这个坑——一个深度超过8000的依赖链递归DFS直接崩了。所以生产环境里更稳妥的做法是用显式栈来实现迭代版DFSdfsIterative(startVertex, callback) { if (!this.adjacencyList.has(startVertex)) return; const visited new Set(); const stack [startVertex]; while (stack.length 0) { const current stack.pop(); if (visited.has(current)) continue; visited.add(current); if (callback) callback(current); const neighbors this.adjacencyList.get(current); for (let i neighbors.length - 1; i 0; i--) { if (!visited.has(neighbors[i])) { stack.push(neighbors[i]); } } } }迭代版DFS有两个容易写错的地方。第一个是邻居入栈的顺序。栈是后进先出所以如果想让遍历顺序和递归版一致也就是先访问第一个邻居需要把邻居列表倒序入栈。上面代码里从neighbors.length - 1开始倒着遍历就是为了保证第一个邻居最后入栈、最先出栈。如果不做这个处理遍历顺序会和递归版相反虽然结果集合相同但在需要确定顺序的场景比如拓扑排序里会出问题。第二个是visited的判断时机。迭代版里我在出栈时判断visited而不是入栈时。这和BFS不同。原因是DFS的栈里可能同时存在多个指向同一顶点的条目如果在入栈时就标记需要额外维护一个已入栈集合在出栈时判断则只需要一个visited集合逻辑更简单。代价是栈里可能有重复元素但总体空间复杂度仍然是O(VE)。递归和迭代两种方式各有适用场景我整理了一个对比对比维度递归DFS迭代DFS代码简洁度高中栈深度限制受引擎限制不受限遍历顺序控制自然需注意入栈顺序调试难度较低中等适合场景小规模图、教学生产环境、大规模图DFS的一个经典应用是检测有向图中是否存在环。思路是维护三个状态集合未访问、正在访问在当前递归路径上、已完成访问。如果在DFS过程中遇到一个正在访问的顶点说明存在环。hasCycle() { const visited new Set(); const inStack new Set(); const dfs (vertex) { visited.add(vertex); inStack.add(vertex); const neighbors this.adjacencyList.get(vertex) || []; for (const neighbor of neighbors) { if (inStack.has(neighbor)) return true; if (!visited.has(neighbor) dfs(neighbor)) return true; } inStack.delete(vertex); return false; }; for (const vertex of this.adjacencyList.keys()) { if (!visited.has(vertex)) { if (dfs(vertex)) return true; } } return false; }这个环检测算法在构建工具里非常实用。比如模块打包时如果模块A依赖BB依赖CC又依赖A就形成了循环依赖打包器需要检测出来并给出警告。inStack集合记录的就是当前DFS路径上的顶点一旦遇到已经在路径上的顶点环就出现了。注意环检测只对有向图有意义。无向图中任意一条边都会形成环因为可以原路返回所以无向图的环检测需要额外记录父节点判断邻居是否是父节点来排除这种情况。4. 两种遍历方式的选型逻辑与真实场景对照BFS和DFS都能遍历图中所有顶点但它们的访问顺序不同导致适用场景也不同。选错了算法可能代码能跑通但性能差很多或者根本解决不了问题。先看一个最典型的场景无权图最短路径。这个问题只能用BFS不能用DFS。原因在于BFS是按距离逐层扩展的第一次到达目标顶点时走过的边数一定是最少的。DFS则可能沿着一条很长的路径先到达目标虽然也是一条路径但不保证最短。我见过有人用DFS做迷宫最短路径结果出来的路径绕了一大圈就是因为DFS不关心距离。反过来拓扑排序问题更适合DFS。拓扑排序要求把有向无环图的顶点排成一个线性序列使得每条边从序列前面的顶点指向后面的顶点。DFS的完成时间也就是顶点从inStack中移除的时刻天然满足这个性质一个顶点完成时它所有能到达的顶点都已经完成了。所以把顶点按完成时间倒序排列就得到拓扑序。topologicalSort() { const visited new Set(); const result []; const dfs (vertex) { visited.add(vertex); const neighbors this.adjacencyList.get(vertex) || []; for (const neighbor of neighbors) { if (!visited.has(neighbor)) { dfs(neighbor); } } result.unshift(vertex); }; for (const vertex of this.adjacencyList.keys()) { if (!visited.has(vertex)) { dfs(vertex); } } return result; }unshift在这里把完成时间晚的顶点放到前面最终result就是拓扑序。如果图中有环拓扑排序无解所以实际使用前通常先用hasCycle检查一下。再看连通分量的问题。判断一个无向图有几个连通分量BFS和DFS都可以。思路是遍历所有顶点对每个未访问的顶点启动一次遍历每次遍历能覆盖到的所有顶点构成一个连通分量。遍历方式用BFS还是DFS不影响结果但BFS通常更快一些因为队列操作比栈操作有更好的缓存局部性。countConnectedComponents() { const visited new Set(); let count 0; for (const vertex of this.adjacencyList.keys()) { if (!visited.has(vertex)) { count; const queue [vertex]; visited.add(vertex); while (queue.length 0) { const current queue.shift(); const neighbors this.adjacencyList.get(current) || []; for (const neighbor of neighbors) { if (!visited.has(neighbor)) { visited.add(neighbor); queue.push(neighbor); } } } } } return count; }这里用了数组的shift()在小规模图上没问题大规模图建议换成前面实现的指针队列。还有一个场景是路径枚举——找出两点之间的所有路径。这个问题必须用DFS因为需要穷举所有可能的分支。BFS只能找到最短路径无法枚举全部路径。DFS在回溯时把当前顶点从路径中移除就能遍历所有可能的路径组合。findAllPaths(start, end) { const paths []; const visited new Set(); const dfs (current, path) { if (current end) { paths.push([...path]); return; } visited.add(current); path.push(current); const neighbors this.adjacencyList.get(current) || []; for (const neighbor of neighbors) { if (!visited.has(neighbor)) { dfs(neighbor, path); } } path.pop(); visited.delete(current); }; dfs(start, []); return paths; }注意这里visited在回溯时要删除因为不同的路径可能经过同一个顶点不能全局标记。这个细节如果搞错会漏掉大量路径。我把常见场景和推荐算法整理成表格方便对照问题类型推荐算法原因无权图最短路径BFS逐层扩展保证首次到达即最短拓扑排序DFS完成时间倒序即拓扑序环检测DFS递归路径状态便于判断回边连通分量BFS/DFS均可两者都能覆盖连通区域路径枚举DFS需要穷举所有分支二分图判断BFS逐层染色更直观迷宫求解BFS需要最短路径表达式求值DFS递归结构天然匹配5. 封装中的性能陷阱与踩坑记录图结构的封装看起来简单但实际写起来有不少细节容易翻车。我把自己踩过的坑和优化经验整理出来这些都是文档里不会写的。第一个坑是顶点标识的类型问题。用Map存储邻接表时键可以是任意类型这本来是优点但如果调用方混用了数字和字符串就会出问题。比如graph.addEdge(1, 2)和graph.addEdge(1, 2)会创建四个不同的顶点因为Map用SameValueZero算法比较键数字1和字符串1不相等。我在一个项目里就遇到过这个问题数据从JSON解析出来是字符串但代码里写的是数字字面量结果图里出现了重复顶点遍历结果完全不对。解决办法是在addVertex和addEdge里统一做类型转换或者在文档里明确约定顶点标识的类型。我倾向于在构造函数里加一个normalize函数默认是String转换调用方可以覆盖。constructor(isDirected false, normalize String) { this.adjacencyList new Map(); this.isDirected isDirected; this.normalize normalize; } addVertex(vertex) { const key this.normalize(vertex); if (!this.adjacencyList.has(key)) { this.adjacencyList.set(key, []); } }第二个坑是删除顶点时的清理工作。删除一个顶点不仅要删掉它在邻接表里的条目还要遍历所有其他顶点的邻居列表把指向它的边也删掉。如果只删了条目其他顶点的邻居列表里还留着这个顶点的引用遍历时会访问到已经不存在的顶点导致undefined错误。removeVertex(vertex) { const key this.normalize(vertex); if (!this.adjacencyList.has(key)) return; this.adjacencyList.delete(key); for (const [v, neighbors] of this.adjacencyList) { const index neighbors.indexOf(key); if (index ! -1) { neighbors.splice(index, 1); } } }这个操作的时间复杂度是O(VE)因为要遍历所有顶点的邻居列表。如果频繁删除顶点邻接表可能不是最优选择需要重新评估数据结构。第三个坑是BFS的visited集合和distancesMap的同步问题。我在一次重构中把visited改成了用数组但distances还是Map结果判断逻辑出现了不一致——数组用includes判断Map用has判断两者对同一个顶点的判断结果不同导致遍历出现死循环。后来统一用Set和Map问题才解决。这个教训是同一份状态不要用两种数据结构表达容易产生不一致。第四个坑是递归DFS的栈溢出。前面提过但这里再强调一下具体的触发条件。JavaScript的调用栈深度限制在不同环境下不同Node.js默认大约是10900层左右浏览器里Chrome大约是10000层。但实际可用的深度还受每个栈帧大小的影响如果DFS函数里局部变量多栈帧大可用深度会更小。我在一个深度约6000的图上用递归DFS就遇到了栈溢出比理论值低不少。解决办法除了改用迭代版还可以用尾递归优化的思路但JavaScript引擎对尾递归的支持并不一致不能依赖。最稳妥的还是迭代版。第五个坑是遍历顺序的不确定性。用Map存储邻接表时Map的迭代顺序是插入顺序这是确定的。但如果邻居列表用Set存储Set的迭代顺序也是插入顺序同样确定。问题出在如果调用方自己传了一个无序的邻居列表或者从外部数据源加载图时顺序不确定遍历结果就会不稳定。在需要确定性输出的场景比如测试断言、快照对比需要先对邻居列表排序。sortNeighbors() { for (const [vertex, neighbors] of this.adjacencyList) { neighbors.sort(); } }排序后遍历顺序就固定了代价是O(E log E)的排序时间。在测试环境里这个代价可以接受生产环境看需求。实操心得调试图算法时把遍历过程可视化出来会事半功倍。我通常会在callback里打印当前顶点和已访问集合或者把遍历顺序记录成数组和预期结果对比。如果图不大还可以用文本画出邻接表的结构一眼就能看出问题。6. 从封装到应用一个依赖分析器的完整实现光有图结构和遍历算法还不够得把它们组合起来解决一个真实问题才能验证封装的完整性。我以一个模块依赖分析器为例展示怎么用这套图结构做实际的事情。假设有一组模块每个模块有名字和它依赖的其他模块列表。我们要做三件事检测是否存在循环依赖、输出一个合法的加载顺序、找出所有被某个模块间接依赖的模块。先构建依赖图function buildDependencyGraph(modules) { const graph new Graph(true); for (const mod of modules) { graph.addVertex(mod.name); for (const dep of mod.dependencies) { graph.addEdge(mod.name, dep); } } return graph; }循环依赖检测直接用前面写的hasCycle。如果返回true说明存在循环依赖需要报错并指出具体的环。要指出环的具体路径需要稍微改造一下hasCycle在检测到回边时记录路径。findCycle() { const visited new Set(); const inStack new Set(); const path []; const dfs (vertex) { visited.add(vertex); inStack.add(vertex); path.push(vertex); const neighbors this.adjacencyList.get(vertex) || []; for (const neighbor of neighbors) { if (inStack.has(neighbor)) { const cycleStart path.indexOf(neighbor); return path.slice(cycleStart).concat(neighbor); } if (!visited.has(neighbor)) { const cycle dfs(neighbor); if (cycle) return cycle; } } inStack.delete(vertex); path.pop(); return null; }; for (const vertex of this.adjacencyList.keys()) { if (!visited.has(vertex)) { const cycle dfs(vertex); if (cycle) return cycle; } } return null; }返回的cycle数组形如[A, B, C, A]清晰地展示了环的路径。这个信息对开发者定位问题非常有用比单纯说存在循环依赖有价值得多。加载顺序用拓扑排序。但要注意依赖图的边方向是模块指向它依赖的模块而加载顺序要求被依赖的模块先加载。所以拓扑排序的结果需要反转或者建图时把边方向反过来。function getLoadOrder(graph) { const cycle graph.findCycle(); if (cycle) { throw new Error(存在循环依赖: ${cycle.join( - )}); } return graph.topologicalSort().reverse(); }反转后的顺序就是合法的加载顺序被依赖的模块排在前面依赖方排在后面。找出所有间接依赖某个模块的模块用反向BFS。先在原图上做一次BFS找到所有直接和间接依赖但方向不对。更直接的做法是构建一个反向图边方向反过来然后在反向图上从目标模块做BFS能到达的所有顶点就是间接依赖它的模块。function findDependents(graph, targetModule) { const reverseGraph new Graph(true); for (const [vertex, neighbors] of graph.adjacencyList) { reverseGraph.addVertex(vertex); for (const neighbor of neighbors) { reverseGraph.addEdge(neighbor, vertex); } } const dependents []; reverseGraph.bfs(targetModule, (vertex) { if (vertex ! targetModule) { dependents.push(vertex); } }); return dependents; }这个功能在评估修改某个模块会影响哪些其他模块时特别有用。改一个底层工具库通过反向BFS就能列出所有受影响的模块帮助评估改动风险。把这三个功能串起来一个简易的依赖分析器就成型了。它验证了图结构封装的完整性addVertex、addEdge、bfs、dfs、hasCycle、topologicalSort这些方法都派上了用场而且组合起来能解决实际问题。我在实际使用这套封装时最大的体会是图算法的价值不在于算法本身多复杂而在于能不能把现实问题抽象成图的问题。一旦抽象对了剩下的就是调用几个现成的方法。依赖分析、社交关系、路径规划、状态机这些问题表面上千差万别但抽象成图之后解法是相通的。封装一套好用的图结构相当于给自己准备了一把万能钥匙遇到新问题先想想能不能用图建模往往能找到意想不到的简洁解法。最后分享一个小技巧在开发阶段给Graph类加一个toString方法用文本形式打印邻接表调试时非常方便。toString() { const lines []; for (const [vertex, neighbors] of this.adjacencyList) { lines.push(${vertex} - ${neighbors.join(, )}); } return lines.join(\n); }输出形如A - B, C B - D C - D D -一眼就能看出图的结构比在调试器里展开Map直观多了。这个方法的实现成本几乎为零但调试效率的提升非常明显。
阅读完成 · 觉得有帮助？
