Sắp xếp topo bằng DFS trong JavaScript

Sắp xếp topo (topological sort) hoặc thứ tự topo của một đồ thị có hướng là một thứ tự tuyến tính các đỉnh sao cho với mọi cạnh có hướng UV từ đỉnh u đến đỉnh v, u xuất hiện trước v trong thứ tự. Điều này chỉ có ý nghĩa trong đồ thị có hướng.

Có nhiều nơi sắp xếp topo rất có ý nghĩa. Ví dụ, giả sử bạn làm theo một công thức nấu ăn, có những bước bắt buộc phải làm trước để đến bước tiếp theo. Nhưng một số bước có thể thực hiện song song. Tương tự, khi chọn môn học đại học, có môn tiên quyết cho môn nâng cao hơn, và môn nâng cao đó lại là tiên quyết cho môn tiếp theo. Ví dụ:

Ví dụ

/**
 *     CS101  CS102
 *     /       \ /
 *   CS204    CS340
 *     \       /| \
 *      CS380  | CS410
 *         \   | /
 *          CS540 */

Trong đồ thị trên, nếu muốn học môn ở một cấp độ, bạn phải học hết các môn nó liên kết từ cấp trên. Dưới đây là một số sắp xếp topo có thể cho đồ thị trên:

CS101 -> CS204 -> CS102 -> CS340 -> CS410 -> CS380 -> CS540
CS102 -> CS101 -> CS340 -> CS204 -> CS410 -> CS380 -> CS540

Hãy triển khai trong JavaScript. Chúng ta sẽ viết 2 hàm: topologicalSort và topologicalSortHelper để hỗ trợ đệ quy đánh dấu và khám phá đồ thị.

Ví dụ

topologicalSortHelper(node, explored, s) {
  explored.add(node);
  // Đánh dấu nút này đã thăm và đi đến các nút
  // phụ thuộc vào nút này, cạnh là node ----> n
  this.edges[node].forEach(n => {
    if (!explored.has(n)) {
      this.topologicalSortHelper(n, explored, s);
    }
  });
  // Tất cả phụ thuộc đã giải quyết cho nút này, ta có thể thêm
  // nút này vào stack.
  s.push(node);
}
topologicalSort() {
  // Tạo Stack để theo dõi tất cả phần tử theo thứ tự đã sắp xếp
  let s = new Stack(this.nodes.length);
  let explored = new Set();
  // Với mỗi nút chưa thăm trong đồ thị, gọi helper.
  this.nodes.forEach(node => {
    if (!explored.has(node)) {
      this.topologicalSortHelper(node, explored, s);
    }
  });
  while (!s.isEmpty()) {
    console.log(s.pop());
  }
}

Bạn có thể kiểm tra bằng cách sau:

Ví dụ

let g = new Graph();
g.addNode("A");
g.addNode("B");
g.addNode("C");
g.addNode("D");
g.addNode("E");
g.addNode("F");
g.addNode("G");
g.addDirectedEdge("A", "C");
g.addDirectedEdge("A", "B");
g.addDirectedEdge("A", "D");
g.addDirectedEdge("C", "D");
g.addDirectedEdge("D", "E");
g.addDirectedEdge("E", "F");
g.addDirectedEdge("B", "G");
g.topologicalSort();

Đồ thị chúng ta tạo trông như:

Ví dụ

/**
 *       A
 *     / | \
 *    C  |  B
 *     \ |  |
 *      D  G
 *      |
 *      E
 *      |
 *      F */

Kết quả

Điều này sẽ cho ra kết quả:

A B G C D E F