Sắp xếp tô pô trong đồ thị là gì?

• Sắp xếp tô pô của một đồ thị có hướng là một thứ tự sắp xếp của các đỉnh sao cho với mọi cung từ đỉnh i đến đỉnh j trong đồ thị, i luôn nằm trước j.

• Sắp xếp tô pô chỉ khả dụng với Đồ thị có hướng không tuần hoàn (DAG).

• Các ứng dụng:

  1. Lập kế hoạch công việc từ các phụ thuộc đã cho giữa các công việc.
  2. Thứ tự đánh giá ô công thức trong bảng tính
  3. Thứ tự các nhiệm vụ biên dịch được thực hiện trong tạo file,
  4. Tuần tự hóa dữ liệu
  5. Giải quyết sự phụ thuộc ký hiệu trong trình liên kết.

Code sắp xếp cấu trúc tô pô trong Java:

    // V - total vertices
    // visited - boolean array to keep track of visited nodes
    // graph - adjacency list.
    // Main Topological Sort Function. 
    void topologicalSort() 
    { 
        Stack<Integer> stack = new Stack<Integer>(); 
  
        // Mark all the vertices as not visited 
        boolean visited[] = new boolean[V]; 
        for (int j = 0; j < V; j++){ 
            visited[j] = false; 
        }
        // C...