答案：图的两种主要表示方法是邻接矩阵和邻接表。邻接矩阵使用二维数组存储边，适合稠密图，检查边存在性快（O(1)），但空间占用大（O(V²)），遍历邻居慢（O(V)）；邻接表使用Map或链表存储每个顶点的邻居，空间效率高（O(V+E)），遍历邻居高效（O(degree(V))），适合稀疏图和图遍历算法，但查边存在性较慢（除非用Set优化）。在JavaScript中实现邻接表时，推荐使用Map+Set组合，以支持任意类型顶点、避免重复边，并提升增删查效率。需注意区分有向与无向图的边处理、防止顶点缺失导致错误、合理选择数据结构以应对自环与多重边，同时关注内存使用与性能优化。
在JavaScript中实现图的邻接表，核心思路是利用哈希映射（通常是
Map
对象）来存储每个顶点，而每个顶点的值则是一个列表（可以是数组或
Set
）来存放其所有相邻的顶点。这就像给每个城市发一张名片，名片上写着它能直达的所有其他城市。这种方式非常直观，也符合我们对“连接”的自然理解。
解决方案
要实现一个图的邻接表，我通常会创建一个
Graph
类，里面用一个
Map
来保存顶点和它们的邻居。
class Graph { constructor() { // 使用Map来存储邻接表，键是顶点，值是该顶点的邻居列表（Set或Array） this.adjacencyList = new Map(); } // 添加一个顶点 addVertex(vertex) { if (!this.adjacencyList.has(vertex)) { this.adjacencyList.set(vertex, new Set()); // 使用Set自动处理重复邻居 } } // 添加一条边（无向图） addEdge(vertex1, vertex2) { if (!this.adjacencyList.has(vertex1)) { this.addVertex(vertex1); } if (!this.adjacencyList.has(vertex2)) { this.addVertex(vertex2); } this.adjacencyList.get(vertex1).add(vertex2); this.adjacencyList.get(vertex2).add(vertex1); // 对于无向图，两边都要加 } // 添加一条边（有向图） addDirectedEdge(source, destination) { if (!this.adjacencyList.has(source)) { this.addVertex(source); } if (!this.adjacencyList.has(destination)) { this.addVertex(destination); } this.adjacencyList.get(source).add(destination); } // 获取某个顶点的所有邻居 getNeighbors(vertex) { return this.adjacencyList.get(vertex) || new Set(); } // 打印图的邻接表 printGraph() { for (let [vertex, neighbors] of this.adjacencyList) { console.log(`${vertex} -> ${[...neighbors].join(', ')}`); } } // 检查两个顶点之间是否存在边 hasEdge(vertex1, vertex2) { return this.adjacencyList.has(vertex1) && this.adjacencyList.get(vertex1).has(vertex2); } // 移除一个顶点及其所有关联的边 removeVertex(vertexToRemove) { if (!this.adjacencyList.has(vertexToRemove)) { return; } // 移除其他顶点到此顶点的边 for (let [vertex, neighbors] of this.adjacencyList) { if (neighbors.has(vertexToRemove)) { neighbors.delete(vertexToRemove); } } // 移除此顶点本身 this.adjacencyList.delete(vertexToRemove); } // 移除一条边 removeEdge(vertex1, vertex2) { if (!this.adjacencyList.has(vertex1) || !this.adjacencyList.has(vertex2)) { return; } this.adjacencyList.get(vertex1).delete(vertex2); this.adjacencyList.get(vertex2).delete(vertex1); // 无向图 }}// 示例用法：const graph = new Graph();graph.addVertex('A');graph.addVertex('B');graph.addVertex('C');graph.addVertex('D');graph.addVertex('E');graph.addEdge('A', 'B');graph.addEdge('A', 'C');graph.addEdge('B', 'D');graph.addEdge('C', 'E');graph.addEdge('D', 'E');console.log("图的邻接表表示：");graph.printGraph();// 输出可能类似：// A -> B, C// B -> A, D// C -> A, E// D -> B, E// E -> C, Dconsole.log(`A和B之间有边吗？ ${graph.hasEdge('A', 'B')}`); // trueconsole.log(`A和D之间有边吗？ ${graph.hasEdge('A', 'D')}`); // falsegraph.removeEdge('A', 'B');console.log("n移除A-B边后：");graph.printGraph();graph.removeVertex('C');console.log("n移除顶点C后：");graph.printGraph();
选择
Map
来作为主容器，而不是普通的JavaScript对象，是因为
Map
的键可以是任意类型（数字、字符串甚至是对象），而普通对象的键最终都会被转成字符串。对于图的顶点，有时候我们可能需要用更复杂的对象来表示，
Map
就显得更灵活。另外，
Set
用于存储邻居列表，可以很方便地确保邻居的唯一性，并且添加、删除操作的平均时间复杂度是O(1)，这对于图的操作来说非常高效。
图的两种主要表示方法有哪些，各有什么优缺点？
在图论中，表示图的方法主要有两种：邻接矩阵（Adjacency Matrix）和邻接表（Adjacency List）。每种方法都有其适用场景和固有的优缺点，了解它们能帮助我们更好地选择适合特定问题的表示方式。
1. 邻接矩阵（Adjacency Matrix）邻接矩阵是一个二维数组（或矩阵），通常记作
A[V][V]
，其中
V
是图中顶点的数量。如果顶点
i
和顶点
j
之间存在一条边，那么
A[i][j]
的值通常设为1（或边的权重）；否则设为0。对于无向图，邻接矩阵是对称的，即
A[i][j] == A[j][i]
。
优点：
快速检查边是否存在： 判断两个顶点之间是否存在边，只需 O(1) 时间复杂度，直接访问
A[i][j]
即可。这在需要频繁查询边是否存在时非常高效。添加/删除边简单： 同样是 O(1) 时间复杂度，直接修改矩阵对应位置的值。易于实现： 概念直观，实现起来相对简单，尤其是在定点数量已知且不经常变化的情况下。稠密图表现好： 对于边数接近
V^2
的稠密图，邻接矩阵的空间利用率相对较高，因为大部分格子都会被填充。
缺点：
空间复杂度高： 无论图中有多少条边，邻接矩阵都需要
O(V^2)
的空间。当顶点数量
V
非常大时，即使图很稀疏（边很少），也会占用大量内存。遍历邻居效率低： 要找到一个顶点的所有邻居，需要遍历该顶点所在行（或列）的所有
V
个元素，时间复杂度是 O(V)。这对于稀疏图来说是很大的浪费。添加/删除顶点复杂： 添加或删除一个顶点需要重新构建整个
V x V
矩阵，或者至少需要调整大量的行和列，这通常是 O(V^2) 的操作。
2. 邻接表（Adjacency List）邻接表是前面我们重点讨论的表示方法。它为图中的每个顶点维护一个列表（通常是链表、数组或哈希集合），该列表存储了所有与该顶点直接相连的顶点。
优点：
空间效率高： 对于稀疏图（边数远小于
V^2
），邻接表的空间复杂度是
O(V + E)
，其中
E
是边的数量。这比邻接矩阵的
O(V^2)
要高效得多。因为只存储了实际存在的边。遍历邻居高效： 要找到一个顶点的所有邻居，只需遍历其对应的邻接列表，时间复杂度是 O(degree(V))，其中
degree(V)
是该顶点的度（即邻居数量）。这通常远小于 O(V)。添加/删除顶点相对灵活： 虽然仍需遍历所有列表来移除相关边，但相比邻接矩阵，操作通常更局部化，理论上比矩阵的 O(V^2) 要好。更适合图遍历算法： 像广度优先搜索（BFS）和深度优先搜索（DFS）等图遍历算法，天然地更适合使用邻接表，因为它们的核心操作就是访问顶点的邻居。
缺点：
检查边是否存在效率低： 判断两个顶点之间是否存在边，需要遍历一个顶点的邻接列表来查找另一个顶点，最坏情况下是 O(degree(V))。如果使用哈希集合（如
Set
）作为邻居列表，可以达到平均 O(1)，但仍比邻接矩阵的O(1)略复杂。实现相对复杂： 相较于简单的二维数组，邻接表的实现需要更多的数据结构（如
Map
和
Set
的组合），逻辑上稍微复杂一些。
总结来说，如果图是稠密的，并且需要频繁检查边是否存在，邻接矩阵可能是更好的选择。而如果图是稀疏的，并且需要频繁遍历顶点的邻居（例如进行图遍历算法），那么邻接表无疑是更优的方案。在实际应用中，绝大多数真实世界的图（如社交网络、互联网拓扑）都是稀疏图，因此邻接表的使用更为广泛。
邻接表在实际应用中如何提高算法效率？
邻接表在图算法中的效率提升，主要体现在它对稀疏图的优化处理上。当图中的边相对较少时，邻接表能够显著减少不必要的计算和内存占用。我个人觉得，它就像一个“按需分配”的系统，只存储必要的信息，而不是像邻接矩阵那样预留一大片可能用不上的空间。
图遍历算法（BFS/DFS）的加速：
这是邻接表最典型的应用场景。广度优先搜索（BFS）和深度优先搜索（DFS）的核心操作都是从一个顶点出发，访问其所有邻居。使用邻接表时，我们直接访问该顶点的邻接列表，遍历其
degree(V)
个邻居，这比邻接矩阵需要遍历
V
个可能为空的位置要快得多。例如，在BFS中，每次从队列中取出一个顶点，然后迭代其邻接表，将未访问的邻居加入队列。这个过程的总时间复杂度是
O(V + E)
，因为每个顶点和每条边都只会被访问常数次。如果用邻接矩阵，遍历邻居的开销会使总复杂度变为
O(V^2)
，当
E
远小于
V^2
时，差距非常明显。
查找最短路径算法（Dijkstra, Bellman-Ford）：
这些算法也需要频繁地访问顶点的邻居。Dijkstra算法在每次扩展时，会从当前顶点检查所有邻居，并更新它们的最短路径估计。邻接表使得“检查邻居”这一步的效率很高，直接迭代邻接列表即可。例如，Dijkstra算法配合优先队列，其时间复杂度可以达到
O(E log V)
或
O(E + V log V)
（取决于优先队列的实现）。如果使用邻接矩阵，则会退化到
O(V^2)
。
最小生成树算法（Prim, Kruskal）：
Prim算法也需要不断地找到当前生成树边缘的最小权重边，并扩展到新的顶点。它同样受益于邻接表高效的邻居访问。Kruskal算法主要关注边的排序，邻接表在这里的优势不如Prim明显，但它仍然是存储边列表的有效方式。
连通性检查与拓扑排序：
这些算法也基于BFS或DFS的变体。例如，判断一个图是否连通，或者找出有向无环图（DAG）的拓扑排序，都依赖于高效地遍历顶点的邻居。邻接表在这里是自然的选择。
空间效率：
除了时间效率，邻接表在空间上的优化也间接提高了算法效率。更少的内存占用意味着更少的缓存未命中，以及在处理大型图时能够避免内存溢出，从而使得算法能够处理更大规模的问题。
说白了，当你的算法需要“沿着边走”时，邻接表就是那个为你铺设好高速公路的工具。它避免了你在一个巨大的、大部分是空的表格中瞎转悠，而是直接告诉你“这里有条路，通向哪里哪里”。这种聚焦于实际存在连接的特性，是它在多数图算法中成为首选表示方法的核心原因。
在JavaScript中实现邻接表时，有哪些需要注意的常见陷阱或优化点？
在JavaScript中实现和使用邻接表，虽然概念上不复杂，但实际操作中还是有些地方需要留心，或者可以进行一些优化，让代码更健壮、更高效。
选择正确的邻居存储结构：
Array
vs.
Set
Array
(数组)： 简单直接，可以存储重复的边（虽然图论中通常认为边是唯一的）。但如果需要检查某个顶点是否是另一个顶点的邻居，或者删除一条边，效率会是 O(degree(V))，因为需要遍历数组。
Set
(集合)： 我个人更倾向于使用
Set
。它自动处理重复的邻居（如果多次尝试添加同一条边，
Set
只会保留一个），并且
add()
,
delete()
,
has()
操作的平均时间复杂度都是 O(1)。这对于图的操作来说非常有利，尤其是在需要频繁检查边是否存在或删除边时。唯一的缺点是，如果需要按特定顺序（比如按顶点ID排序）遍历邻居，
Set
需要先转换为数组。陷阱： 如果用
Array
存储邻居，但在
addEdge
时没有检查重复，可能会导致逻辑错误或不必要的重复计算。
处理自环和多重边：
自环： 顶点连接到自身。邻接表天然支持自环，只需在邻接列表中将顶点自己添加到自己的邻居列表中即可。多重边： 两个顶点之间有多条边。如果使用
Set
存储邻居，多重边会被自动去重，只保留一条。如果需要支持多重边（例如在表示网络流量或多条路径时），那么邻居列表就不能用
Set
，而应该用
Array
，并且在添加边时直接
push
进去，不做去重处理。这取决于你的图模型是否允许多重边。
无向图与有向图的边处理：
无向图： 每条边
(u, v)
意味着
u
连接
V
，同时
V
也连接
u
。所以在
addEdge(u, v)
时，你需要同时在
u
的邻接列表中添加
V
，也在
V
的邻接列表中添加
u
。有向图： 边
(u, v)
意味着从
u
到
V
有一条方向，但
V
到
u
不一定有。所以只需要在
u
的邻接列表中添加
V
。陷阱： 忘记区分这两种情况，或者在实现时混淆，会导致图的结构不正确。我的代码示例中提供了
addEdge
(无向) 和
addDirectedEdge
(有向) 两种方法，就是为了避免这种混淆。
顶点不存在时的健壮性处理：
在
addEdge
或
getNeighbors
等方法中，始终要检查顶点是否存在于
adjacencyList
中。如果尝试添加边到不存在的顶点，或者获取不存在顶点的邻居，应该先添加该顶点，或者返回一个空集/错误，而不是让程序崩溃。我的代码中就包含了这种检查。
内存管理与垃圾回收：
在JavaScript中，虽然我们不需要手动管理内存，但了解引用关系有助于避免内存泄漏。当一个图不再需要时，确保所有对图对象的引用都被清除，这样垃圾回收器才能释放其占用的内存。对于大型图，这一点尤为重要。
性能优化：
对于非常大的图，如果顶点是字符串或者数字，
Map
的性能通常很好。但如果顶点是复杂对象，
Map
默认使用引用相等性来比较键，这可能不是你想要的。在这种情况下，你可能需要为顶点定义一个唯一的ID，并用ID作为
Map
的键。避免在循环中重复进行昂贵的操作，例如重复创建
new Set()
或
new Map()
实例。
调试和可视化：
当图变得复杂时，仅仅
console.log
打印邻接表可能不足以帮助理解图的结构。可以考虑使用一些图可视化库（如 D3.js, Cytoscape.js）来帮助调试和展示图的结构，这在大型项目或教学中非常有用。
这些“坑”或者说“细节”，很多时候都是在实际开发中踩过才有的体会。一开始可能觉得一个
Map
加上
Set
就搞定了，但随着图的规模和操作的复杂性增加，这些细节就变得越来越关键了。
以上就是JS如何实现图的邻接表？图的表示方法的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1516197.html
微信扫一扫 
支付宝扫一扫 
