如何实现非递归的服务全量依赖（含次级依赖）高效查询

实现思路 #

采用广度优先搜索(BFS)的迭代实现，完全避免递归调用栈溢出风险，时间复杂度为O(n)（n为全量依赖节点总数），每个依赖节点仅会被处理1次，天然适配无循环依赖的业务场景，也可自动对重复依赖做去重。

基础实现代码 #

function getAllDependencies(serviceName, primaryDependencies) {
  const allDeps = new Set();
  // 初始化队列，先塞入目标服务的一级依赖
  const queue = [...(primaryDependencies[serviceName] || [])];
  let index = 0;

  // 用指针替代shift操作，避免数组头部弹出的性能损耗
  while (index < queue.length) {
    const currentDep = queue[index++];
    // 跳过已经处理过的依赖，避免重复添加
    if (allDeps.has(currentDep)) continue;
    allDeps.add(currentDep);
    // 将当前依赖的下级依赖加入队列
    const subDeps = primaryDependencies[currentDep] || [];
    queue.push(...subDeps);
  }

  // 将集合转成数组返回，顺序和依赖遍历顺序一致
  return Array.from(allDeps);
}

测试用例验证 #

我们用题目给出的依赖对象测试：

const primaryDependencies = {
  'service1': ['service2'],
  'service2': ['service3', 'service4'],
  'service3': ['service7'],
  'service4': ['service5'],
  'service5': [],
  'service6': ['service7'],
  'service7': []
}

// 测试service1
console.log(getAllDependencies('service1', primaryDependencies)) 
// 输出：['service2', 'service3', 'service4', 'service7', 'service5'] 和示例1一致

// 测试service4
console.log(getAllDependencies('service4', primaryDependencies))
// 输出：['service5'] 和示例2一致

方案优势 #

• 无递归调用栈溢出风险，即便是依赖层级超过1000+的深链路场景也能正常运行
• 天然支持去重，即便是多个链路依赖同一个服务，也不会出现重复结果
• 时间效率最优，所有节点仅遍历一次，队列操作均为O(1)复杂度

内容的提问来源于stack exchange，提问作者Anand Krishnan