JavaScript 中 Set 怎么实现图论算法中的已访问节点-js教程-PHP中文网

set是图论算法中“已访问节点”集合的理想选择，因其o(1)平均时间复杂度的插入、查找、删除，自动去重且语义清晰；数组查找为o(n)，对象有原型污染和类型转换问题，map功能冗余。

javascript 中 set 怎么实现图论算法中的已访问节点

JavaScript 中的 Set 是实现图论算法中“已访问节点”集合的理想选择，因为它天然支持 O(1) 平均时间复杂度的插入、查找和删除操作，且自动去重、语义清晰。

为什么用 Set 而不是数组或对象？

对比常见替代方案：

数组（Array）：用 includes() 查找是 O(n)，遍历图时频繁查重会导致整体性能退化为 O(V×E)，不推荐；
普通对象（{}）：虽支持 O(1) 属性访问，但需手动处理键名类型（如数字节点转字符串）、存在原型污染风险，且语义不明确；
Map：功能强大但过度设计——我们只需要“是否存在”，不需要关联值；
Set：专为“唯一值集合”设计，has()/add() 直观高效，支持任意类型（包括对象、Symbol），语义精准。

基础用法：BFS/DFS 中标记已访问

以邻接表表示的有向图为例：

Alibabacloud Sdk Client Initialization For Java

在 Java 中初始化和管理阿里云 SDK客户端。包括单例模式、线程安全、endpoint 与 region 配置、VPC 终端节点、同步与异步等。

下载

const graph = {
  A: ['B', 'C'],
  B: ['D'],
  C: ['D'],
  D: []
};

function bfs(start) {
  const visited = new Set(); // ✅ 核心：记录已访问节点
  const queue = [start];

  while (queue.length > 0) {
    const node = queue.shift();
    if (visited.has(node)) continue; // ✅ O(1) 判断是否已访问
    visited.add(node);             // ✅ O(1) 标记为已访问

    console.log(node);
    for (const neighbor of graph[node] || []) {
      if (!visited.has(neighbor)) {
        queue.push(neighbor);
      }
    }
  }
}
bfs('A'); // 输出 A → B → C → D

进阶注意：节点类型与引用问题

当图节点是对象（而非字符串/数字）时，Set 默认按引用比较：

const nodeA = { id: 'A' };
const nodeB = { id: 'B' };
const visited = new Set();

visited.add(nodeA);
console.log(visited.has({ id: 'A' })); // ❌ false —— 新对象，引用不同

解决方式：