javascript数组怎么实现邻接表-js教程-PHP中文网

javascript数组怎么实现邻接表

畫卷琴夢

发布： 2025-07-30 09:04:01

原创

973人浏览过

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

javascript数组怎么实现邻接表

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

解决方案：

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

立即学习“Java免费学习笔记（深入）”；

如何高效地用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)。

落笔AI

AI写作，AI写网文、AI写长篇小说、短篇小说

查看详情

实际上，如果需要频繁地检查某个顶点是否是另一个顶点的邻居，那么可以使用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算法等其他重要的图算法。

以上就是javascript数组怎么实现邻接表的详细内容，更多请关注php中文网其它相关文章！