TopologicalSorter [拓扑排序器]

# 介绍

拓扑排序要解决的问题是给一个图的所有节点排序。拓扑排序是指图中顶点的线性排序，使得对于每条从顶点 u 到顶点 v 的有向边 u -> v，顶点 u 都排在顶点 v 之前。

# 实现

# JavaScript

export function TopologicalSorter () {
  const graph = {}
  let isVisitedNode
  let finishTimeCount
  let finishingTimeList
  let nextNode

  this.addOrder = function (nodeA, nodeB) {
    nodeA = String(nodeA)
    nodeB = String(nodeB)
    graph[nodeA] = graph[nodeA] || []
    graph[nodeA].push(nodeB)
  }

  this.sortAndGetOrderedItems = function () {
    isVisitedNode = Object.create(null)
    finishTimeCount = 0
    finishingTimeList = []

    for (const node in graph) {
      if (Object.prototype.hasOwnProperty.call(graph, node) && !isVisitedNode[node]) {
        dfsTraverse(node)
      }
    }

    finishingTimeList.sort(function (item1, item2) {
      return item1.finishTime > item2.finishTime ? -1 : 1
    })

    return finishingTimeList.map(function (value) { return value.node })
  }

  function dfsTraverse (node) {
    isVisitedNode[node] = true
    if (graph[node]) {
      for (let i = 0; i < graph[node].length; i++) {
        nextNode = graph[node][i]
        if (isVisitedNode[nextNode]) continue
        dfsTraverse(nextNode)
      }
    }

    finishingTimeList.push({
      node,
      finishTime: ++finishTimeCount
    })
  }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

# 参考

编辑

上次更新: 2022/05/10, 23:46:22

← TimSort [Tim 排序] WiggleSort [摆动排序]→