給定一個服務物件及其主要依賴項，找到每個服務的所有依賴項（包括次要依賴項）

例如，假設我們有一個像

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

我想找到給定服務的所有依賴項。通過所有依賴項，我的意思是原始服務的每個主要依賴項的主要依賴項 主要依賴項。（注意 - 我們現在可以忽略回圈依賴）

示例 1，對于服務 1

primaryDependencies = ['service2']
allDependencies = [ 'service2', 'service3', 'service4', 'service7', 'service5' ]

示例 2，對于服務 4

primaryDependencies = ['service5']
allDependencies = ['service5']

到目前為止我所做的（REPL - https://replit.com/@pcajanand/CreepyFumblingInformation#index.js）

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

const getDependentServices = (service) => {
  return primaryDependencies[service]
}

const main = () => {

console.log('service1', findAllDependents('service1', []))
console.log('service2', findAllDependents('service2', []))
console.log('service3', findAllDependents('service3', []))
console.log('service4', findAllDependents('service4', []))
console.log('service5', findAllDependents('service5', []))
console.log('service6', findAllDependents('service6', []))
console.log('service7', findAllDependents('service7', []))
}


const findAllDependents = (service, visited) => {
  let allDeps = []
  const directDeps = getDependentServices(service)
  allDeps = allDeps.concat(directDeps)
  visited.push(service)
  if (allDeps.length > 0) {
    allDeps.forEach(dep => {
      if (visited.indexOf(dep) === -1) {
        allDeps = allDeps.concat(findAllDependents(dep, visited), allDeps)
      } else {
        throw new Error('Possible circular dependency')
      }
      visited.push(dep)
    })
  }
  let set = new Set(allDeps)
  set.delete(service)
  return [...set]
}

main()

尋找一個高效和優化的解決方案，最好沒有任何遞回。

謝謝閱讀！祝你今天過得愉快...

uj5u.com熱心網友回復：

這可以通過廣度優先搜索來處理，這是一種樹遍歷演算法。請注意，這沒有任何遞回。

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

console.log(bfs(primaryDependencies, 'service1'));

// breadth-first search
function bfs(input, key) {
  const output = {
    primaryDependencies: [],
    allDependencies: []
  };

  const root = input[key];
  if (!root) {
    return output;
  }

  output.primaryDependencies = root;
  output.allDependencies = [...root];

  const queue = [];
  queue.push(...root);

  while (queue.length) {
    const size = queue.length;
    for (let i = 0; i < size; i  ) {
      const curr = queue.shift();
      const children = input[curr];
      for (let j = 0; j < children.length; j  ) {
        output.allDependencies.push(children[j]);
        queue.push(children[j]);
      }
    }
  }

  // Using Set in order to remove possible duplicates
  output.allDependencies = new Set(output.allDependencies);
  output.allDependencies = [...output.allDependencies];

  return output;
}

uj5u.com熱心網友回復：

您可以采用較小的方法并采用Set收集和檢查。

const
    getDependencies = (dependencies, key, s = new Set) => {
        if (s.has(key)) throw new Error('Circular dependency');
        s.add(key);
        dependencies[key].forEach(k => {
            if (s.has(k)) return;
            getDependencies(dependencies, k, s);
        });
        return [...s];
    },
    primaryDependencies = { service1: ['service2'], service2: ['service3', 'service4'], service3: ['service7'], service4: ['service5'], service5: [], service6: ['service7'], service7: [] };

Object.keys(primaryDependencies).forEach(k => console.log(...getDependencies(primaryDependencies, k)));

.as-console-wrapper { max-height: 100% !important; top: 0; }

標籤：javascript 数组 json 算法 递归

上一篇：如何通過for回圈將矩陣的值賦給陣列

下一篇：如何使用Python從輸入陣列中生成最大數？