图的邻接表实现方法详解

文章不知道大家是否熟悉？今天我将给大家介绍《JS图的邻接表实现方法详解》，这篇文章主要会讲到等等知识点，如果你在看完本篇文章后，有更好的建议或者发现哪里有问题，希望大家都能积极评论指出，谢谢！希望我们能一起加油进步！

答案：图的两种主要表示方法是邻接矩阵和邻接表。邻接矩阵使用二维数组存储边，适合稠密图，检查边存在性快（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, 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]，其中 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的组合），逻辑上稍微复杂一些。

总结来说，如果图是稠密的，并且需要频繁检查边是否存在，邻接矩阵可能是更好的选择。而如果图是稀疏的，并且需要频繁遍历顶点的邻居（例如进行图遍历算法），那么邻接表无疑是更优的方案。在实际应用中，绝大多数真实世界的图（如社交网络、互联网拓扑）都是稀疏图，因此邻接表的使用更为广泛。

邻接表在实际应用中如何提高算法效率？

邻接表在图算法中的效率提升，主要体现在它对稀疏图的优化处理上。当图中的边相对较少时，邻接表能够显著减少不必要的计算和内存占用。我个人觉得，它就像一个“按需分配”的系统，只存储必要的信息，而不是像邻接矩阵那样预留一大片可能用不上的空间。

1. 图遍历算法（BFS/DFS）的加速：

   • 这是邻接表最典型的应用场景。广度优先搜索（BFS）和深度优先搜索（DFS）的核心操作都是从一个顶点出发，访问其所有邻居。
   • 使用邻接表时，我们直接访问该顶点的邻接列表，遍历其 degree(V) 个邻居，这比邻接矩阵需要遍历 V 个可能为空的位置要快得多。
   • 例如，在BFS中，每次从队列中取出一个顶点，然后迭代其邻接表，将未访问的邻居加入队列。这个过程的总时间复杂度是 O(V + E)，因为每个顶点和每条边都只会被访问常数次。如果用邻接矩阵，遍历邻居的开销会使总复杂度变为 O(V^2)，当 E 远小于 V^2 时，差距非常明显。

2. 查找最短路径算法（Dijkstra, Bellman-Ford）：

   • 这些算法也需要频繁地访问顶点的邻居。Dijkstra算法在每次扩展时，会从当前顶点检查所有邻居，并更新它们的最短路径估计。
   • 邻接表使得“检查邻居”这一步的效率很高，直接迭代邻接列表即可。
   • 例如，Dijkstra算法配合优先队列，其时间复杂度可以达到 O(E log V) 或 O(E + V log V)（取决于优先队列的实现）。如果使用邻接矩阵，则会退化到 O(V^2)。

3. 最小生成树算法（Prim, Kruskal）：

   • Prim算法也需要不断地找到当前生成树边缘的最小权重边，并扩展到新的顶点。它同样受益于邻接表高效的邻居访问。
   • Kruskal算法主要关注边的排序，邻接表在这里的优势不如Prim明显，但它仍然是存储边列表的有效方式。

4. 连通性检查与拓扑排序：

   • 这些算法也基于BFS或DFS的变体。例如，判断一个图是否连通，或者找出有向无环图（DAG）的拓扑排序，都依赖于高效地遍历顶点的邻居。邻接表在这里是自然的选择。

5. 空间效率：

   • 除了时间效率，邻接表在空间上的优化也间接提高了算法效率。更少的内存占用意味着更少的缓存未命中，以及在处理大型图时能够避免内存溢出，从而使得算法能够处理更大规模的问题。

说白了，当你的算法需要“沿着边走”时，邻接表就是那个为你铺设好高速公路的工具。它避免了你在一个巨大的、大部分是空的表格中瞎转悠，而是直接告诉你“这里有条路，通向哪里哪里”。这种聚焦于实际存在连接的特性，是它在多数图算法中成为首选表示方法的核心原因。

在JavaScript中实现邻接表时，有哪些需要注意的常见陷阱或优化点？

在JavaScript中实现和使用邻接表，虽然概念上不复杂，但实际操作中还是有些地方需要留心，或者可以进行一些优化，让代码更健壮、更高效。

1. 选择正确的邻居存储结构：Array vs. Set

   • Array (数组)： 简单直接，可以存储重复的边（虽然图论中通常认为边是唯一的）。但如果需要检查某个顶点是否是另一个顶点的邻居，或者删除一条边，效率会是 O(degree(V))，因为需要遍历数组。
   • Set (集合)： 我个人更倾向于使用 Set。它自动处理重复的邻居（如果多次尝试添加同一条边，Set只会保留一个），并且 add(), delete(), has() 操作的平均时间复杂度都是 O(1)。这对于图的操作来说非常有利，尤其是在需要频繁检查边是否存在或删除边时。唯一的缺点是，如果需要按特定顺序（比如按顶点ID排序）遍历邻居，Set需要先转换为数组。
   • 陷阱： 如果用 Array 存储邻居，但在 addEdge 时没有检查重复，可能会导致逻辑错误或不必要的重复计算。

2. 处理自环和多重边：

   • 自环： 顶点连接到自身。邻接表天然支持自环，只需在邻接列表中将顶点自己添加到自己的邻居列表中即可。
   • 多重边： 两个顶点之间有多条边。如果使用 Set 存储邻居，多重边会被自动去重，只保留一条。如果需要支持多重边（例如在表示网络流量或多条路径时），那么邻居列表就不能用 Set，而应该用 Array，并且在添加边时直接 push 进去，不做去重处理。这取决于你的图模型是否允许多重边。

3. 无向图与有向图的边处理：

   • 无向图： 每条边 (u, v) 意味着 u 连接 v，同时 v 也连接 u。所以在 addEdge(u, v) 时，你需要同时在 u 的邻接列表中添加 v，也在 v 的邻接列表中添加 u。
   • 有向图： 边 (u, v) 意味着从 u 到 v 有一条方向，但 v 到 u 不一定有。所以只需要在 u 的邻接列表中添加 v。
   • 陷阱： 忘记区分这两种情况，或者在实现时混淆，会导致图的结构不正确。我的代码示例中提供了 addEdge (无向) 和 addDirectedEdge (有向) 两种方法，就是为了避免这种混淆。

4. 顶点不存在时的健壮性处理：

   • 在 addEdge 或 getNeighbors 等方法中，始终要检查顶点是否存在于 adjacencyList 中。如果尝试添加边到不存在的顶点，或者获取不存在顶点的邻居，应该先添加该顶点，或者返回一个空集/错误，而不是让程序崩溃。我的代码中就包含了这种检查。

5. 内存管理与垃圾回收：

   • 在JavaScript中，虽然我们不需要手动管理内存，但了解引用关系有助于避免内存泄漏。当一个图不再需要时，确保所有对图对象的引用都被清除，这样垃圾回收器才能释放其占用的内存。对于大型图，这一点尤为重要。

6. 性能优化：

   • 对于非常大的图，如果顶点是字符串或者数字，Map 的性能通常很好。但如果顶点是复杂对象，Map 默认使用引用相等性来比较键，这可能不是你想要的。在这种情况下，你可能需要为顶点定义一个唯一的ID，并用ID作为 Map 的键。
   • 避免在循环中重复进行昂贵的操作，例如重复创建 new Set() 或 new Map() 实例。

7. 调试和可视化：

   • 当图变得复杂时，仅仅 console.log 打印邻接表可能不足以帮助理解图的结构。可以考虑使用一些图可视化库（如 D3.js, Cytoscape.js）来帮助调试和展示图的结构，这在大型项目或教学中非常有用。

这些“坑”或者说“细节”，很多时候都是在实际开发中踩过才有的体会。一开始可能觉得一个 Map 加上 Set 就搞定了，但随着图的规模和操作的复杂性增加，这些细节就变得越来越关键了。

到这里，我们也就讲完了《图的邻接表实现方法详解》的内容了。个人认为，基础知识的学习和巩固，是为了更好的将其运用到项目中，欢迎关注golang学习网公众号，带你了解更多关于的知识点！