拓扑排序

拓扑排序定义即说明：https://zh.wikipedia.org/zh-hans/%E6%8B%93%E6%92%B2%E6%8E%92%E5%BA%8F

• 特别说明：只有有向无环图 (opens new window)才能被排序

卡恩算法

卡恩于 1962 年提出的算法。简单来说就是，假设 L 是存放结果的列表，先找到那些入度为零的节点，把这些节点放到 L 中，因为这些节点没有任何的父节点。然后把与这些节点相连的边从图中去掉，再寻找图中的入度为零的节点。对于新找到的这些入度为零的节点来说，他们的父节点已经都在 L 中了，所以也可以放入 L。重复上述操作，直到找不到入度为零的节点。如果此时 L 中的元素个数和节点总数相同，说明排序完成；如果 L 中的元素个数和节点总数不同，说明原图中存在环，无法进行拓扑排序。

举个例子

index.js对cdns.js中的 CDN 列表进行排序，根据相互依赖关系生成 script 标签插入到 html 中，此时就需要排出他们之间的顺序，确保 CDN 引入成功

cdns.js

module.exports = [
  {
    name: '@uyun-cdn',
    dependencies: []
  },
  {
    name: '@uyun-charts',
    dependencies: ['@uyun-cdn', 'classnames-bundle', 'lodash-bundle', 'react-bundle', 'redux-bundle']
  },
  {
    name: '@uyun-components',
    dependencies: ['@uyun-cdn', 'classnames-bundle', 'lodash-bundle', 'moment-bundle', 'react-bundle']
  },
  {
    name: '@uyun-ec-basic-layout',
    dependencies: ['@uyun-cdn', '@uyun-components', 'react-bundle']
  },
  {
    name: '@uyun-utils',
    dependencies: ['@uyun-cdn', 'axios-bundle']
  },
  {
    name: 'axios-bundle',
    dependencies: ['@uyun-cdn']
  },
  {
    name: 'classnames-bundle',
    dependencies: ['@uyun-cdn']
  },
  {
    name: 'lodash-bundle',
    dependencies: ['@uyun-cdn']
  },
  {
    name: 'mobx-bundle',
    dependencies: ['@uyun-cdn', 'react-bundle']
  },
  {
    name: 'moment-bundle',
    dependencies: ['@uyun-cdn']
  },
  {
    name: 'react-bundle',
    dependencies: ['@uyun-cdn']
  },
  {
    name: 'react-router-bundle',
    dependencies: ['@uyun-cdn', 'react-bundle']
  },
  {
    name: 'redux-bundle',
    dependencies: ['@uyun-cdn', 'react-bundle']
  },
  {
    name: 'rxjs-bundle',
    dependencies: ['@uyun-cdn']
  }
]

index.js

const cdns = require('./cdns')

// 生成新对象，方便排序
const bundles = cdns.map(cdn => ({
  ...cdn,
  deps: new Set(cdn.dependencies)
}))

/**
 * 拓扑排序（卡恩算法）
 * 把未排序的和已排序的分别放入两个数组
 * 遇到没有依赖的项目，push到已排序数组
 * 删掉未排序集合中这一个项目的依赖
 * 不断循环，直到未排序数组长度为0
 * 如果中途存在未排序的数组长度等于传进来的集合长度
 * 说明存在循环依赖，不能排序
 * 参考：https://zh.wikipedia.org/wiki/%E6%8B%93%E6%92%B2%E6%8E%92%E5%BA%8F
 * @param {Array} bundles
 */
function topologicalSort(bundles) {
  const sorted = []
  const unsorted = []

  bundles.forEach(bundle => {
    if (bundle.deps && !bundle.deps.size) {
      sorted.push(bundle)
      bundles.forEach(({ deps }) => deps.delete(bundle.name))
    } else {
      unsorted.push(bundle)
    }
  })

  if (bundles.length && bundles.length === unsorted.length) throw new Error('存在循环依赖，cdn不能排序')
  if (unsorted.length) sorted.push(...topologicalSort(unsorted))
  return sorted
}

console.log(topologicalSort(bundles).map(({ name }) => name))