Topological Sorting ด้วย JavaScript DFS

Topological sort หรือ topological ordering ของ directed graph คือ linear ordering ของ vertices ที่สำหรับทุก directed edge UV จาก vertex u ไป vertex v u จะมาก่อน v ใน ordering นี้มีความหมายเฉพาะใน directed graphs

มีหลายที่ที่ topological sort นำไปใช้ได้ เช่น ตามสูตรอาหาร มี steps ที่ต้องทำก่อนถึง step ถัดไป แต่บาง steps ทำพร้อมกันได้ คล้ายกับการเลือกวิชาในมหาวิทยาลัย มี prerequisites สำหรับวิชาขั้นสูง ซึ่งอาจเป็น prerequisites สำหรับวิชาต่อไปอีก เช่น:

ตัวอย่าง

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

ใน graph ข้างต้น ถ้าอยากเรียนวิชาในระดับหนึ่ง ต้องเรียนวิชาที่เชื่อมมาจากระดับบนก่อน ต่อไปนี้เป็น topological sorts ที่เป็นไปได้:

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

มานำไปใช้ใน JavaScript เราจะเขียน 2 ฟังก์ชัน topological sort และ topologicalSortHelper เพื่อช่วย recursively mark และ explore graph:

ตัวอย่างโค้ด

topologicalSortHelper(node, explored, s) {
  explored.add(node);
  // mark node นี้ visited และไป nodes ที่ dependent บน node นี้ edge คือ node ----> n
  this.edges[node].forEach(n => {
    if (!explored.has(n)) {
      this.topologicalSortHelper(n, explored, s);
    }
  });
  // dependencies ทั้งหมด resolved สำหรับ node นี้ เพิ่มเข้า stack
  s.push(node);
}
topologicalSort() {
  // สร้าง Stack เก็บ elements ใน sorted order
  let s = new Stack(this.nodes.length);
  let explored = new Set();
  // สำหรับทุก unvisited node เรียก helper
  this.nodes.forEach(node => {
    if (!explored.has(node)) {
      this.topologicalSortHelper(node, explored, s);
    }
  });
  while (!s.isEmpty()) {
    console.log(s.pop());
  }
}

ทดสอบการทำงานได้ดังนี้:

ตัวอย่างการใช้งาน

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();

Graph ที่เราสร้าง長這樣:

ตัวอย่าง

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

ผลลัพธ์

จะได้ผลลัพธ์ดังนี้:

A B G C D E F