JS如何实现图的邻接表？图的表示方法-js教程-PHP中文网

答案：图的两种主要表示方法是邻接矩阵和邻接表。邻接矩阵使用二维数组存储边，适合稠密图，检查边存在性快（O(1)），但空间占用大（O(V²)），遍历邻居慢（O(V)）；邻接表使用Map或链表存储每个顶点的邻居，空间效率高（O(V+E)），遍历邻居高效（O(degree(V))），适合稀疏图和图遍历算法，但查边存在性较慢（除非用Set优化）。在JavaScript中实现邻接表时，推荐使用Map+Set组合，以支持任意类型顶点、避免重复边，并提升增删查效率。需注意区分有向与无向图的边处理、防止顶点缺失导致错误、合理选择数据结构以应对自环与多重边，同时关注内存使用与性能优化。

js如何实现图的邻接表？图的表示方法

在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, D

console.log(`A和B之间有边吗？ ${graph.hasEdge('A', 'B')}`); // true
console.log(`A和D之间有边吗？ ${graph.hasEdge('A', 'D')}`); // false

graph.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]

登录后复制

，其中

登录后复制

是图中顶点的数量。如果顶点

登录后复制

和顶点

登录后复制

之间存在一条边，那么

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）：

爱图表
AI驱动的智能化图表创作平台

99

查看详情
- 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）来帮助调试和展示图的结构，这在大型项目或教学中非常有用。