Sắp xếp tôpô hay thứ tự tôpô của đồ thị có hướng là một thứ tự tuyến tính của các đỉnh của nó sao cho mọi cạnh có hướng UV từ đỉnh u đến đỉnh v, u đến trước v theo thứ tự. Điều này chỉ có ý nghĩa trong các biểu đồ có hướng.
Có rất nhiều nơi mà việc sắp xếp topo có rất nhiều ý nghĩa. Ví dụ:giả sử bạn đang làm theo một công thức, trong phần này, có một số bước cần thiết để chuyển sang các bước tiếp theo. Nhưng một số trong số này có thể được thực hiện song song. Tương tự như vậy, trong quá trình học đại học khi lựa chọn các khóa học, có một số điều kiện tiên quyết cho các khóa học nâng cao hơn mà bản thân chúng có thể là điều kiện tiên quyết cho các khóa học tiếp theo. Ví dụ -
Ví dụ
/** * CS101 CS102 * / \ / * CS204 CS340 * \ /| \ * CS380 | CS410 * \ | / * CS540 */
Trong biểu đồ trên, hãy xem xét nếu bạn muốn tham gia khóa học ở một cấp độ, Trước tiên, bạn sẽ phải tham gia tất cả các khóa học mà nó được kết nối từ cấp độ trên nó. Sau đây là một số cách sắp xếp tôpô có thể có cho biểu đồ trên -
CS101 -> CS204 -> CS102 -> CS340 -> CS410 -> CS380 -> CS540 CS102 -> CS101 -> CS340 -> CS204 -> CS410 -> CS380 -> CS540
Hãy để chúng tôi thực hiện điều này trong JavaScript. Chúng tôi sẽ viết 2 hàm, sắp xếp topo và topologicalSortHelper để giúp đánh dấu và khám phá đồ thị một cách đệ quy.
Ví dụ
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());
}
} Bạn có thể kiểm tra điều này bằng cách sử dụng -
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(); Biểu đồ chúng tôi đã tạo trông giống như -
Ví dụ
/** * A * / | \ * C | B * \ | | * D G * | * E * | * F */
Đầu ra
Điều này sẽ cung cấp đầu ra -
A B G C D E F