JS数组构建邻接表详解

从现在开始，努力学习吧！本文《JS数组构建邻接表教程》主要讲解了等等相关知识点，我会在golang学习网中持续更新相关的系列文章，欢迎大家关注并积极留言建议。下面就先一起来看一下本篇正文内容吧，希望能帮到你！

最高效的方式是使用Map结合Set来表示邻接表，1. 当顶点编号不连续或数量大时，使用Map以顶点为键存储邻居列表，避免空间浪费；2. 使用Set代替数组存储邻居，使检查邻居关系的时间复杂度降为O(1)；3. 对于添加和删除边操作，需在无向图中同步更新双向边，使用push和filter或Set的add/delete方法实现；4. 该结构广泛应用于DFS、BFS、Dijkstra等图算法，提供高效的邻接关系查询与遍历支持。

在JavaScript中，数组可以巧妙地模拟邻接表，用来表示图结构。核心思路是用数组的索引代表图中的顶点，而每个索引对应的值（通常也是一个数组）则存储与该顶点相邻的顶点。

解决方案：

JavaScript数组实现邻接表，关键在于利用数组的索引作为顶点，数组元素存储相邻顶点。

如何高效地用JavaScript数组表示图的邻接关系？

用JavaScript数组表示图的邻接关系，本质上是建立顶点和其相邻顶点之间的映射。最直接的方法是使用一个数组，数组的每个索引代表一个顶点，而索引对应的值则是一个数组，存储与该顶点相邻的所有顶点。

例如，如果图中有顶点0, 1, 2, 3，并且顶点0与顶点1和2相邻，顶点1与顶点0和3相邻，顶点2与顶点0相邻，顶点3与顶点1相邻，那么邻接表可以表示为：

const adjacencyList = [
  [1, 2], // 顶点0的邻居是1和2
  [0, 3], // 顶点1的邻居是0和3
  [0],    // 顶点2的邻居是0
  [1]     // 顶点3的邻居是1
];

这种表示方法的优点是简单直观，易于理解和实现。但是，如果图的顶点数量非常大，或者顶点编号不连续，那么使用数组可能会浪费大量的存储空间。此外，查找特定顶点的邻居的时间复杂度是O(1)，但是检查某个顶点是否是另一个顶点的邻居的时间复杂度是O(n)，其中n是邻居的数量。

为了解决这些问题，可以使用JavaScript的Map对象来代替数组。Map对象可以存储任意类型的键值对，因此可以使用顶点作为键，邻居列表作为值。例如：

const adjacencyList = new Map();
adjacencyList.set(0, [1, 2]);
adjacencyList.set(1, [0, 3]);
adjacencyList.set(2, [0]);
adjacencyList.set(3, [1]);

使用Map对象的好处是可以灵活地表示顶点编号不连续的图，并且可以避免浪费存储空间。但是，查找特定顶点的邻居的时间复杂度仍然是O(1)，检查某个顶点是否是另一个顶点的邻居的时间复杂度仍然是O(n)。

实际上，如果需要频繁地检查某个顶点是否是另一个顶点的邻居，那么可以使用Set对象来存储邻居列表。Set对象可以高效地检查某个元素是否存在。例如：

const adjacencyList = new Map();
adjacencyList.set(0, new Set([1, 2]));
adjacencyList.set(1, new Set([0, 3]));
adjacencyList.set(2, new Set([0]));
adjacencyList.set(3, new Set([1]));

在这种表示方法中，检查某个顶点是否是另一个顶点的邻居的时间复杂度是O(1)。

选择哪种表示方法取决于具体的应用场景。如果顶点数量不大，并且顶点编号连续，那么使用数组是最简单的选择。如果顶点数量很大，或者顶点编号不连续，那么使用Map对象可以更好地利用存储空间。如果需要频繁地检查邻居关系，那么使用Set对象可以提高性能。

如何在邻接表中添加和删除边？

在基于数组的邻接表中添加边，我们需要找到对应顶点的数组，并将新的邻居添加到该数组中。删除边则需要从邻居数组中移除指定的顶点。注意，如果是无向图，则需要在两个顶点对应的数组中都进行操作。

function addEdge(graph, source, destination) {
  graph[source].push(destination); // 添加边

  // 如果是无向图，则需要添加反向边
  // graph[destination].push(source);
}

function removeEdge(graph, source, destination) {
  graph[source] = graph[source].filter(neighbor => neighbor !== destination);

  // 如果是无向图，则需要移除反向边
  // graph[destination] = graph[destination].filter(neighbor => neighbor !== source);
}

// 示例
const adjacencyList = [[1, 2], [0, 3], [0], [1]];
addEdge(adjacencyList, 0, 3); // 添加从顶点0到顶点3的边
console.log(adjacencyList); // 输出：[ [ 1, 2, 3 ], [ 0, 3 ], [ 0 ], [ 1 ] ]

removeEdge(adjacencyList, 0, 2); // 移除从顶点0到顶点2的边
console.log(adjacencyList); // 输出：[ [ 1, 3 ], [ 0, 3 ], [ 0 ], [ 1 ] ]

需要注意的是，在实际应用中，可能需要进行错误处理，例如检查顶点是否存在，以及避免添加重复的边。

邻接表在图算法中的应用实例

邻接表是实现许多图算法的基础。例如，深度优先搜索 (DFS) 和广度优先搜索 (BFS) 都可以很方便地使用邻接表来实现。

下面是一个使用邻接表实现DFS的JavaScript示例：

function dfs(graph, startNode, visited = new Set()) {
  visited.add(startNode);
  console.log(`Visiting node: ${startNode}`);

  for (const neighbor of graph[startNode]) {
    if (!visited.has(neighbor)) {
      dfs(graph, neighbor, visited);
    }
  }
}

// 示例
const adjacencyList = [[1, 2], [0, 3], [0], [1]];
dfs(adjacencyList, 0);
// 输出：
// Visiting node: 0
// Visiting node: 1
// Visiting node: 3
// Visiting node: 2

在这个例子中，dfs 函数递归地访问图中的每个顶点。visited Set用于跟踪已经访问过的顶点，以避免无限循环。 类似地，BFS也可以使用邻接表来实现，只需要使用队列来代替递归调用即可。 此外，邻接表还可以用于实现Dijkstra算法、Prim算法等其他重要的图算法。

文中关于map,JS数组,set,邻接表,图结构的知识介绍，希望对你的学习有所帮助！若是受益匪浅，那就动动鼠标收藏这篇《JS数组构建邻接表详解》文章吧，也可关注golang学习网公众号了解相关技术文章。