การเรียงลำดับทอพอโลยีหรือการจัดลำดับทอพอโลยีของกราฟกำกับเป็นการเรียงลำดับเชิงเส้นของจุดยอดในลักษณะที่ว่าสำหรับรังสีอัลตราไวโอเลตทุกเส้นจากจุดยอด u ถึงจุดยอด v u มาก่อน v ในลำดับ สิ่งนี้สมเหตุสมผลในกราฟกำกับเท่านั้น
มีหลายสถานที่ที่การเรียงลำดับทอพอโลยีเหมาะสมอย่างยิ่ง ตัวอย่างเช่น สมมติว่าคุณกำลังทำตามสูตร ในส่วนนี้มีขั้นตอนบางอย่างที่จำเป็นสำหรับการไปยังขั้นตอนถัดไป แต่บางส่วนสามารถทำได้ควบคู่กันไป ในทำนองเดียวกัน ระหว่างเรียนในวิทยาลัยเมื่อเลือกหลักสูตร มีข้อกำหนดเบื้องต้นบางประการสำหรับหลักสูตรขั้นสูง ซึ่งอาจเป็นข้อกำหนดเบื้องต้นสำหรับหลักสูตรเพิ่มเติม ตัวอย่างเช่น −
ตัวอย่าง
/** * CS101 CS102 * / \ / * CS204 CS340 * \ /| \ * CS380 | CS410 * \ | / * CS540 */
ในกราฟด้านบน ให้พิจารณาว่าคุณต้องการเรียนหลักสูตรในระดับใดระดับหนึ่งหรือไม่ คุณจะต้องเลือกหลักสูตรทั้งหมดที่เชื่อมโยงจากระดับที่สูงกว่านั้นก่อน ต่อไปนี้เป็นการเรียงลำดับทอพอโลยีที่เป็นไปได้สำหรับกราฟด้านบน -
CS101 -> CS204 -> CS102 -> CS340 -> CS410 -> CS380 -> CS540 CS102 -> CS101 -> CS340 -> CS204 -> CS410 -> CS380 -> CS540
ให้เราปรับใช้สิ่งนี้ใน JavaScript เราจะเขียน 2 ฟังก์ชัน ได้แก่ การเรียงลำดับทอพอโลยี และทอพอโลยีSortHelper เพื่อช่วยทำเครื่องหมายและสำรวจกราฟแบบเรียกซ้ำ
ตัวอย่าง
topologicalSortHelper(node, explored, s) {
explored.add(node);
// Marks this node as visited and goes on to the nodes
// that are dependent on this node, the edge is node ----> n
this.edges[node].forEach(n => {
if (!explored.has(n)) {
this.topologicalSortHelper(n, explored, s);
}
});
// All dependencies are resolved for this node, we can now add
// This to the stack.
s.push(node);
}
topologicalSort() {
// Create a Stack to keep track of all elements in sorted order
let s = new Stack(this.nodes.length);
let explored = new Set();
// For every unvisited node in our graph, call the 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(); กราฟที่เราสร้างดูเหมือน -
ตัวอย่าง
/** * A * / | \ * C | B * \ | | * D G * | * E * | * F */
ผลลัพธ์
สิ่งนี้จะให้ผลลัพธ์ -
A B G C D E F
