By

文章目錄

最近在学习数据结构，就试着用JavaScript来实现一些基本数据结构。本文介绍的主要是拓扑排序JavaScript实现。

拓扑排序是对有向无圈图（DAG）的一种排序，它使得如果存在一条从vi到vj的路径，那么在排序中vj必须出现在vi后面。

如果图是有圈的，那么拓扑排序是不可能的。因为对于两个圈上的两个顶点v和w，v先于w，w又同时先于v。

拓扑排序的实现原理：

  1. 从 DAG 图中选择一个 没有前驱（即入度为0）的顶点并输出
  2. 从图中删除该顶点和所有以它为起点的有向边
  3. 重复 1 和 2 直到当前的 DAG 图为空或当前图中不存在无前驱的顶点为止。后一种情况说明有向图中必然存在环。

enter image description here

以上得到拓扑排序后的结果是 { 1, 2, 4, 3, 5 }

下面是JavaScript的实现：

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
function EdgeNode (id) {
  this.id = id;
  this.afters = [];
  this.indegree = 0;
}

function topsort (edges) {
  var nodes = {};
  var result = [];
  var queue = [];

  // build data structres
  edges.forEach(function (edge) {
    var fromEdge = edge[0];
    var fromStr = fromEdge.toString();
    var fromNode;

    if (!(fromNode = nodes[fromStr])) {
      fromNode = nodes[fromStr] = new EdgeNode(fromEdge);
    }

    edge.forEach(function (toEdge) {
      // since from and to are in same array, we'll always see from again, so make sure we skip it..
      if (toEdge == fromEdge) {
        return;
      }

      var toEdgeStr = toEdge.toString();

      if (!nodes[toEdgeStr]) {
        nodes[toEdgeStr] = new EdgeNode(toEdge);
      }
      nodes[toEdgeStr].indegree++;
      fromNode.afters.push(toEdge);
    });
  });

  // topsort
  var keys = Object.keys(nodes);
  keys.forEach(function (key) {
    if (nodes[key].indegree === 0) {
      queue.push(key);
    }
  });
  while (queue.length !== 0) {
    let vertex = queue.shift();
    result.push(nodes[vertex].id);

    nodes[vertex].afters.forEach(function (after) {
      var afterStr = after.toString();

      nodes[afterStr].indegree--;
      if (nodes[afterStr].indegree === 0) {
        queue.push(afterStr);
      }
    });
  }

  return result;
}

var edges = [
    ['two', 'three'],
    ['four', 'six'],
    ['one', 'three'],
    ['two', 'four'],
    ['six', 'nine'],
    ['five', 'seven'],
    ['five', 'eight'],
    ['five', 'nine'],
    ['seven', 'eight'],
    ['eight', 'nine'],
    ['one', 'two'],
    ['four', 'five'],
    ['four', 'six'],
    ['three', 'six'],
    ['six', 'seven'],
    ['three', 'four']
];
var sorted = topsort(edges);
console.log(sorted);

以上参考链接：

文章目錄