拓扑排序

概念

拓扑排序(Topological Sort)是有向图中所有结点的一种线性次序，即最终的排序结果一定要符合图中的先后方向。也就是说拓扑排序是存在多解或者无解的可能，显然有向环不存在拓扑排序。
详细概念这篇文章还是讲得挺细致的，包括全序/偏序概念。
其实现有Kahn算法(类似BFS)和DFS算法，分别如下图所示。

Kahn算法

DFS算法

---

LeetCode之拓扑排序

269.Alien Dictionary
输入一组已排序单词，破解词汇的先后顺序（若有多个返回一个）；若不存在返回空。

 Input:  [
  "wrt",
  "wrf",
  "er",
  "ett",
  "rftt"
  ]
 Output: "wertf"

用Kahn算法进行拓扑排序即可，关键在于建立邻接表，注意不是单个单词中字符存在顺序，而是用前后单词中的顺序关系来建立图模型。

var allienDict = function (words) {
  var len = 26, base = 'a'.charCodeAt(0);
  var inDegree = new Array(len).fill(-1);
  var neighbors = [];
  for (var i = 0; i < len; i++) {
    neighbors.push([]);
  }
  for (i = 0; i < words.length - 1; i++) {
    var minLen = Math.min(words[i].length, words[i + 1].length);
    for (var j = 0; j < minLen; j++) {
      if (words[i][j] != words[i + 1][j]) {
        var x = words[i].charCodeAt(j) - base, y = words[i + 1].charCodeAt(j) - base;
        if (inDegree[x] == -1) inDegree[x] = 0;
        if (inDegree[y] != -1) {
          inDegree[y]++;
        } else {
          inDegree[y] = 1;
        }
        neighbors[x].push(y);
        break;
      }
    }
  }
  var queue = [], count = 0, sum = 0, res = "";
  for (i = 0; i < 26; i++) {
    if (inDegree[i] == 0) queue.push(i);
    if (inDegree[i] >= 0) sum++;
  }
  while (queue.length !== 0) {
    count++;
    var tmp = queue.shift();
    res += String.fromCharCode(tmp + base);
    for (i = 0; i < neighbors[tmp].length; i++) {
      if (--inDegree[neighbors[tmp][i]] === 0) queue.push(neighbors[tmp][i]);
    }
  }
  //if the total count of order < the total node counts
  return count == sum ? res : "";
};

444.Sequence Reconstruction
判断系列是否由有向系列组成全序，若非全序或者无拓扑序都返回false

Input: org: [1,2,3], seqs: [[1,2],[1,3],[2,3]]
Output: True
Input: [1,2,3], seqs: [[1,2],[1,3]]
Output: False

本来觉得检查系列临近的有向边是否在输入的有向系列存在即可；但是这样一来无法判断有向系列是否存在环。还是需要进行拓扑排序，若每次入度为0的结点多于1个，即是偏序；若最后拓扑排序结点数小于总结点，即存在环。

var constructSequences = function (org, seqs) {
  var len = org.length;
  var neighbors = {}, inDegree = {};
  for (var i = 0; i < seqs.length; i++) {
    for (var j = 0; j < seqs[i].length - 1; j++) {
      var first = seqs[i][j], second = seqs[i][j + 1];
      //in
      if (neighbors[first] == undefined) neighbors[first] = {};
      if (inDegree[first] == undefined) inDegree[first] = 0;
      //out
      if (inDegree[second] == undefined) inDegree[second] = 0;
      if (neighbors[first][second] == undefined) {
        neighbors[first][second] = 1;
        inDegree[second]++;
      }
    }
  }
  console.log("inDegree:", inDegree);
  console.log("neighbors:", neighbors);
  var queue = [], count = 0;
  for (var item in inDegree) {
    if (inDegree[item] == 0) queue.push(item);
  }
  while (queue.length > 0) {
    if (queue.length > 1) return false;
    count++;
    var node = queue.shift();
    for (item in neighbors[node]) {
      if (--inDegree[item] == 0) queue.push(item);
    }

  }
  return count == len;
};