Bài 19.2: Sắp xếp tô-pô và ứng dụng

Chào mừng trở lại với series bài viết về Cấu trúc dữ liệu và Giải thuật! Hôm nay, chúng ta sẽ đi sâu vào một khái niệm cực kỳ hữu ích trong lý thuyết đồ thị: Sắp xếp tô-pô (Topological Sort). Đây là một kỹ thuật mạnh mẽ giúp chúng ta tổ chức và hiểu được mối quan hệ phụ thuộc giữa các đối tượng, thường được biểu diễn dưới dạng đồ thị.

Sắp xếp tô-pô là gì?

Hãy tưởng tượng bạn có một danh sách các công việc cần làm, nhưng một số công việc phải hoàn thành trước khi công việc khác có thể bắt đầu. Ví dụ, bạn không thể mặc áo khoác trước khi mặc áo sơ mi, hoặc bạn không thể thi môn "Giải thuật" nếu chưa học xong môn "Cấu trúc dữ liệu". Đây chính là những mối quan hệ phụ thuộc.

Trong thế giới của đồ thị, những mối quan hệ này có thể được biểu diễn bằng các đồ thị có hướng. Mỗi công việc hoặc đối tượng là một đỉnh (vertex), và một cạnh có hướng từ đỉnh A sang đỉnh B (A -> B) có nghĩa là A phải hoàn thành trước B.

Sắp xếp tô-pô là một thứ tự tuyến tính của tất cả các đỉnh trong đồ thị có hướng sao cho với mọi cạnh có hướng từ đỉnh u đến đỉnh v, thì u luôn xuất hiện trước v trong thứ tự đó.

Điều quan trọng cần lưu ý là Sắp xếp tô-pô chỉ tồn tại đối với Đồ thị có hướng không chu trình (Directed Acyclic Graph - DAG). Nếu đồ thị chứa một chu trình, ví dụ: A -> B -> C -> A, thì không thể nào tìm được thứ tự tuyến tính thỏa mãn điều kiện, bởi vì A cần trước B, B cần trước C, và C lại cần trước A - một vòng lặp không thể phá vỡ.

Tại sao Sắp xếp tô-pô lại quan trọng?

Nó cho phép chúng ta xác định một trình tự hợp lệ để xử lý hoặc thực hiện các tác vụ có phụ thuộc lẫn nhau. Hãy nghĩ về nó như việc lên kế hoạch một cách logic để đảm bảo mọi thứ diễn ra đúng trình tự.

Lập lịch các công việc: Xác định thứ tự thực hiện các tác vụ xây dựng, sản xuất, hoặc các bước trong một quy trình phức tạp.
Xử lý phụ thuộc: Trong quản lý gói phần mềm (như apt, yum, npm), Sắp xếp tô-pô được dùng để cài đặt các gói theo đúng thứ tự phụ thuộc.
Biên dịch mã nguồn: Xác định thứ tự biên dịch các module hoặc file nguồn dựa trên các khai báo include hoặc import.
Xây dựng quy trình dữ liệu: Xác định thứ tự xử lý các bước trong một pipeline dữ liệu.
Lập lịch học tập: Xác định thứ tự các môn học dựa trên môn tiên quyết.

Các Thuật toán Sắp xếp tô-pô

Có hai thuật toán phổ biến để tìm sắp xếp tô-pô trên một DAG:

Thuật toán Kahn (Sử dụng đếm bậc vào - In-degree): Thuật toán này dựa trên ý tưởng liên tục loại bỏ các đỉnh không còn phụ thuộc chưa được xử lý.
Thuật toán dựa trên DFS (Duyệt theo chiều sâu): Thuật toán này sử dụng quá trình duyệt DFS và thêm đỉnh vào kết quả sau khi đã thăm hết các đỉnh mà nó có cạnh đi tới.

Chúng ta sẽ khám phá chi tiết cả hai thuật toán này.

1. Thuật toán Kahn

Thuật toán Kahn hoạt động như sau:

Bước 1: Tính bậc vào (in-degree) của tất cả các đỉnh. Bậc vào của một đỉnh là số lượng cạnh đi vào đỉnh đó. Một đỉnh có bậc vào bằng 0 không có bất kỳ phụ thuộc nào chưa được xử lý.
Bước 2: Khởi tạo một hàng đợi (queue) và thêm tất cả các đỉnh có bậc vào bằng 0 vào hàng đợi này. Đây là những đỉnh có thể được xử lý đầu tiên.
Bước 3: Khởi tạo một danh sách rỗng để lưu kết quả sắp xếp tô-pô.
Bước 4: Chừng nào hàng đợi còn phần tử:
- Lấy một đỉnh u từ phía trước hàng đợi.
- Thêm u vào danh sách kết quả.
- Với mỗi đỉnh v là hàng xóm của u (tức là có cạnh u -> v):
  - Giảm bậc vào của v đi 1 (vì phụ thuộc vào u đã được xử lý).
  - Nếu bậc vào của v trở thành 0, thêm v vào hàng đợi.
Bước 5: Sau khi vòng lặp kết thúc, nếu số lượng đỉnh trong danh sách kết quả bằng tổng số đỉnh trong đồ thị, thì danh sách kết quả chính là một sắp xếp tô-pô hợp lệ. Nếu không, đồ thị chứa chu trình.

Ưu điểm của thuật toán Kahn là nó tự nhiên phát hiện chu trình và dễ dàng triển khai bằng cấu trúc dữ liệu hàng đợi.

Hãy xem một ví dụ minh họa bằng C++.

Giả sử đồ thị có 6 đỉnh (đánh số từ 0 đến 5) và các cạnh: 0 -> 1 0 -> 2 1 -> 3 2 -> 3 2 -> 4 3 -> 5 4 -> 5

Bậc vào ban đầu: Đỉnh 0: 0 Đỉnh 1: 1 (từ 0) Đỉnh 2: 1 (từ 0) Đỉnh 3: 2 (từ 1, 2) Đỉnh 4: 1 (từ 2) Đỉnh 5: 2 (từ 3, 4)

Các đỉnh có bậc vào 0: chỉ có đỉnh 0.

Quá trình:

Hàng đợi: [0]. Kết quả: []
Lấy 0. Kết quả: [0].
- Giảm bậc vào của hàng xóm 1: in_degree[1] = 0. Hàng đợi: [1].
- Giảm bậc vào của hàng xóm 2: in_degree[2] = 0. Hàng đợi: [1, 2].
Lấy 1. Kết quả: [0, 1].
- Giảm bậc vào của hàng xóm 3: in_degree[3] = 1. Hàng đợi: [2].
Lấy 2. Kết quả: [0, 1, 2].
- Giảm bậc vào của hàng xóm 3: in_degree[3] = 0. Hàng đợi: [3].
- Giảm bậc vào của hàng xóm 4: in_degree[4] = 0. Hàng đợi: [3, 4].
Lấy 3. Kết quả: [0, 1, 2, 3].
- Giảm bậc vào của hàng xóm 5: in_degree[5] = 1. Hàng đợi: [4].
Lấy 4. Kết quả: [0, 1, 2, 3, 4].
- Giảm bậc vào của hàng xóm 5: in_degree[5] = 0. Hàng đợi: [5].
Lấy 5. Kết quả: [0, 1, 2, 3, 4, 5].
- Không có hàng xóm. Hàng đợi: [].

Hàng đợi trống. Kích thước kết quả (6) bằng tổng số đỉnh (6). Sắp xếp tô-pô hợp lệ tìm được: [0, 1, 2, 3, 4, 5]. Một sắp xếp tô-pô khác cũng có thể là [0, 2, 1, 3, 4, 5] hoặc [0, 2, 4, 1, 3, 5], v.v., tùy thuộc vào thứ tự lấy các đỉnh có cùng bậc vào 0 từ hàng đợi.

Code minh họa (C++):

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm> // Để sử dụng std::vector

// Hàm thực hiện Sắp xếp tô-pô bằng thuật toán Kahn
std::vector<int> topologicalSortKahn(int V, const std::vector<std::vector<int>>& adj) {
    // V: số đỉnh
    // adj: danh sách kề biểu diễn đồ thị

    // 1. Tính bậc vào của tất cả các đỉnh
    std::vector<int> in_degree(V, 0);
    for (int u = 0; u < V; ++u) {
        for (int v : adj[u]) {
            in_degree[v]++;
        }
    }

    // 2. Khởi tạo hàng đợi và thêm các đỉnh có bậc vào 0
    std::queue<int> q;
    for (int i = 0; i < V; ++i) {
        if (in_degree[i] == 0) {
            q.push(i);
        }
    }

    // 3. Khởi tạo danh sách kết quả
    std::vector<int> result;
    int count = 0; // Đếm số đỉnh được xử lý

    // 4. Xử lý hàng đợi
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        result.push_back(u);
        count++;

        // Duyệt qua các hàng xóm của u
        for (int v : adj[u]) {
            in_degree[v]--;
            // Nếu bậc vào của hàng xóm trở thành 0, thêm vào hàng đợi
            if (in_degree[v] == 0) {
                q.push(v);
            }
        }
    }

    // 5. Kiểm tra chu trình
    if (count != V) {
        // Đồ thị có chu trình, không thể tìm được sắp xếp tô-pô
        // Trả về danh sách rỗng hoặc báo lỗi tùy thuộc vào yêu cầu
        std::cerr << "Error: Graph contains a cycle!" << std::endl;
        return {}; // Trả về danh sách rỗng để báo hiệu lỗi
    }

    return result;
}

int main() {
    // Ví dụ đồ thị
    int V = 6; // 6 đỉnh
    std::vector<std::vector<int>> adj(V);

    // Thêm các cạnh (đánh số đỉnh từ 0)
    adj[0].push_back(1);
    adj[0].push_back(2);
    adj[1].push_back(3);
    adj[2].push_back(3);
    adj[2].push_back(4);
    adj[3].push_back(5);
    adj[4].push_back(5);

    std::vector<int> topo_order = topologicalSortKahn(V, adj);

    if (!topo_order.empty()) {
        std::cout << "Mot sap xep to-po cua do thi la:" << std::endl;
        for (int i = 0; i < topo_order.size(); ++i) {
            std::cout << topo_order[i] << (i == topo_order.size() - 1 ? "" : " -> ");
        }
        std::cout << std::endl;
    } else {
        std::cout << "Khong the tim thay sap xep to-po (do thi co chu trinh)." << std::endl;
    }

    // Ví dụ đồ thị có chu trình (thêm cạnh 5 -> 0)
    std::cout << "\nTest voi do thi co chu trinh (them canh 5 -> 0):" << std::endl;
    std::vector<std::vector<int>> adj_cycle = adj; // Sao chép đồ thị cũ
    adj_cycle[5].push_back(0); // Thêm cạnh 5 -> 0
    std::vector<int> topo_order_cycle = topologicalSortKahn(V, adj_cycle);

    if (!topo_order_cycle.empty()) {
         std::cout << "Mot sap xep to-po cua do thi co chu trinh la:" << std::endl;
         for (int i = 0; i < topo_order_cycle.size(); ++i) {
             std::cout << topo_order_cycle[i] << (i == topo_order_cycle.size() - 1 ? "" : " -> ");
         }
         std::cout << std::endl;
    } else {
         std::cout << "Khong the tim thay sap xep to-po (do thi co chu trinh)." << std::endl;
    }


    return 0;
}

Giải thích code Kahn:

std::vector<std::vector<int>> adj: Biểu diễn đồ thị bằng danh sách kề. adj[u] chứa danh sách các đỉnh v mà có cạnh từ u đến v.
std::vector<int> in_degree(V, 0): Mảng lưu trữ bậc vào của mỗi đỉnh. Khởi tạo tất cả là 0.
Vòng lặp đầu tiên để tính toán in_degree: Duyệt qua tất cả các cạnh (bằng cách duyệt qua danh sách kề của mỗi đỉnh) và tăng bậc vào của đỉnh đích.
std::queue<int> q: Hàng đợi dùng để lưu trữ các đỉnh có bậc vào hiện tại bằng 0.
Vòng lặp thứ hai thêm các đỉnh có bậc vào 0 ban đầu vào hàng đợi.
std::vector<int> result: Vector để lưu trữ kết quả sắp xếp tô-pô.
count: Biến đếm số đỉnh đã được thêm vào result.
Vòng lặp while (!q.empty()): Đây là trung tâm của thuật toán. Chúng ta lấy đỉnh u từ hàng đợi, thêm vào kết quả, tăng count. Sau đó, với mỗi hàng xóm v của u, chúng ta giảm in_degree[v]. Nếu in_degree[v] trở thành 0, nghĩa là tất cả các phụ thuộc của v đã được xử lý, nên v sẵn sàng và được thêm vào hàng đợi.
Kiểm tra if (count != V): Nếu sau khi xử lý hết hàng đợi mà số đỉnh trong kết quả không bằng tổng số đỉnh của đồ thị, điều đó chỉ xảy ra khi còn các đỉnh có bậc vào lớn hơn 0 nhưng lại không thể truy cập được từ bất kỳ đỉnh nào có bậc vào 0 ban đầu - dấu hiệu của một chu trình.

2. Thuật toán dựa trên DFS

Thuật toán dựa trên DFS hoạt động dựa trên nguyên tắc rằng một đỉnh chỉ được thêm vào danh sách sắp xếp tô-pô sau khi tất cả các đỉnh mà nó trỏ tới (các phụ thuộc của nó) đã được xử lý. Quá trình này tương tự như duyệt cây theo kiểu post-order traversal.

Bước 1: Sử dụng một mảng visited để theo dõi trạng thái của các đỉnh trong quá trình DFS. Chúng ta cần ba trạng thái:
- 0: Chưa được thăm (unvisited).
- 1: Đang được thăm (visiting - đang trong stack đệ quy hiện tại).
- 2: Đã thăm xong (visited - đã ra khỏi stack đệ quy và tất cả các đỉnh con đã được xử lý).
Bước 2: Sử dụng một cấu trúc dữ liệu (như std::list trong C++ hoặc stack tạm thời) để lưu trữ kết quả. Các đỉnh sẽ được thêm vào trước các đỉnh đã thăm xong sau chúng.
Bước 3: Duyệt qua tất cả các đỉnh của đồ thị. Nếu một đỉnh chưa được thăm (trạng thái 0), gọi hàm DFS đệ quy cho đỉnh đó.
Bước 4: Hàm DFS cho đỉnh u:
- Đánh dấu u là đang được thăm (trạng thái 1).
- Đối với mỗi hàng xóm v của u:
  - Nếu v đang ở trạng thái đang thăm (1), đồ thị có chu trình. Dừng lại và báo lỗi.
  - Nếu v chưa được thăm (0), gọi đệ quy DFS(v). Nếu cuộc gọi đệ quy này phát hiện chu trình, dừng lại và trả về tín hiệu lỗi.
- Đánh dấu u là đã thăm xong (trạng thái 2).
- Thêm u vào phía trước của danh sách kết quả.
Bước 5: Nếu quá trình DFS hoàn tất mà không phát hiện chu trình, danh sách kết quả chính là một sắp xếp tô-pô.

Phát hiện chu trình trong thuật toán DFS rất trực quan: nếu trong quá trình DFS từ đỉnh u, chúng ta gặp lại một đỉnh v đang ở trạng thái "đang thăm" (trạng thái 1), điều đó có nghĩa là có một đường đi từ v đến u và chúng ta đang đi ngược trở lại trong cùng một đường đi đệ quy, tạo thành một chu trình.

Hãy xem ví dụ đồ thị tương tự với thuật toán DFS.

Giả sử đồ thị có 6 đỉnh (đánh số từ 0 đến 5) và các cạnh: 0 -> 1 0 -> 2 1 -> 3 2 -> 3 2 -> 4 3 -> 5 4 -> 5

Quá trình (DFS): Kết quả: list rỗng Visited_state: [0, 0, 0, 0, 0, 0]

Bắt đầu DFS từ đỉnh 0 (chưa thăm).
- dfs_visit(0):
  - visited_state[0] = 1 (đang thăm).
  - Neighbors của 0: 1, 2.
  - Gọi dfs_visit(1) (1 chưa thăm):
    - visited_state[1] = 1.
    - Neighbors của 1: 3.
    - Gọi dfs_visit(3) (3 chưa thăm):
      - visited_state[3] = 1.
      - Neighbors của 3: 5.
      - Gọi dfs_visit(5) (5 chưa thăm):
        
        visited_state[5] = 1.
        
        Neighbors của 5: không có.
        
        visited_state[5] = 2 (đã thăm xong).
        
        Thêm 5 vào trước kết quả. Kết quả: [5].
      - dfs_visit(5) kết thúc.
      - Neighbors của 3 đã xong.
      - visited_state[3] = 2.
      - Thêm 3 vào trước kết quả. Kết quả: [3, 5].
    - dfs_visit(3) kết thúc.
    - Neighbors của 1 đã xong.
    - visited_state[1] = 2.
    - Thêm 1 vào trước kết quả. Kết quả: [1, 3, 5].
  - dfs_visit(1) kết thúc.
  - Neighbors của 0: tiếp tục với 2. Gọi dfs_visit(2) (2 chưa thăm):
    - visited_state[2] = 1.
    - Neighbors của 2: 3, 4.
    - Neighbor 3: đã thăm xong (state 2). Bỏ qua.
    - Neighbor 4: chưa thăm. Gọi dfs_visit(4):
      - visited_state[4] = 1.
      - Neighbors của 4: 5.
      - Neighbor 5: đã thăm xong (state 2). Bỏ qua.
      - visited_state[4] = 2.
      - Thêm 4 vào trước kết quả. Kết quả: [4, 1, 3, 5]. (hoặc [4, 3, 5, 1] nếu list được cập nhật lại) -> List: [4] rồi add [1,3,5] -> [4,1,3,5] là sai logic. Thêm 4 vào trước list hiện tại ([1, 3, 5]) -> [4, 1, 3, 5]. Lưu ý: việc thêm vào list thường là list.push_front().
      - Thêm 4 vào trước list [1, 3, 5] -> [4, 1, 3, 5] (list.push_front(4) trên list [1, 3, 5]).
    - dfs_visit(4) kết thúc.
    - Neighbors của 2 đã xong.
    - visited_state[2] = 2.
    - Thêm 2 vào trước kết quả. Kết quả: [2, 4, 1, 3, 5].
  - dfs_visit(2) kết thúc.
  - Neighbors của 0 đã xong.
  - visited_state[0] = 2.
  - Thêm 0 vào trước kết quả. Kết quả: [0, 2, 4, 1, 3, 5].
- dfs_visit(0) kết thúc.
Kiểm tra các đỉnh khác (1, 2, 3, 4, 5). Tất cả đều đã thăm (state 2).
Không phát hiện chu trình. Kết quả: [0, 2, 4, 1, 3, 5] là một sắp xếp tô-pô hợp lệ.

Code minh họa (C++):

#include <iostream>
#include <vector>
#include <list> // Sử dụng std::list để thêm phần tử vào đầu dễ dàng
#include <algorithm> // Để sử dụng std::vector

// Hàm DFS đệ quy cho Sắp xếp tô-pô
// visited_state: 0 = unvisited, 1 = visiting, 2 = visited
bool dfs_visit(int u, std::vector<int>& visited_state, const std::vector<std::vector<int>>& adj, std::list<int>& result_list) {
    // Nếu đang trong quá trình thăm lại u, có chu trình
    if (visited_state[u] == 1) {
        return true; // Báo hiệu tìm thấy chu trình
    }
    // Nếu đã thăm xong u, không cần thăm lại
    if (visited_state[u] == 2) {
        return false; // Không tìm thấy chu trình
    }

    // Đánh dấu u là đang thăm
    visited_state[u] = 1;

    // Thăm tất cả các hàng xóm của u
    for (int v : adj[u]) {
        if (dfs_visit(v, visited_state, adj, result_list)) {
            return true; // Truyền báo hiệu chu trình ngược lên
        }
    }

    // Đã thăm xong u và tất cả các đỉnh con của nó
    visited_state[u] = 2;
    // Thêm u vào đầu danh sách kết quả (vì nó phải đứng trước các đỉnh mà nó trỏ tới)
    result_list.push_front(u);

    return false; // Không tìm thấy chu trình từ đỉnh này
}

// Hàm chính thực hiện Sắp xếp tô-pô bằng DFS
std::vector<int> topologicalSortDFS(int V, const std::vector<std::vector<int>>& adj) {
    // V: số đỉnh
    // adj: danh sách kề

    std::vector<int> visited_state(V, 0); // Khởi tạo tất cả là chưa thăm (0)
    std::list<int> result_list; // Sử dụng list để thêm vào đầu
    bool cycle_found = false;

    // Duyệt qua tất cả các đỉnh để đảm bảo xử lý cả đồ thị không liên thông
    for (int i = 0; i < V; ++i) {
        if (visited_state[i] == 0) { // Nếu đỉnh chưa được thăm
            if (dfs_visit(i, visited_state, adj, result_list)) {
                cycle_found = true;
                break; // Tìm thấy chu trình, dừng lại
            }
        }
    }

    if (cycle_found) {
        std::cerr << "Error: Graph contains a cycle!" << std::endl;
        return {}; // Trả về vector rỗng để báo hiệu lỗi
    }

    // Chuyển kết quả từ list sang vector
    std::vector<int> result_vector(result_list.begin(), result_list.end());
    return result_vector;
}

int main() {
    // Ví dụ đồ thị (giống ví dụ trên)
    int V = 6; // 6 đỉnh
    std::vector<std::vector<int>> adj(V);

    // Thêm các cạnh (đánh số đỉnh từ 0)
    adj[0].push_back(1);
    adj[0].push_back(2);
    adj[1].push_back(3);
    adj[2].push_back(3);
    adj[2].push_back(4);
    adj[3].push_back(5);
    adj[4].push_back(5);

    std::vector<int> topo_order = topologicalSortDFS(V, adj);

    if (!topo_order.empty()) {
        std::cout << "Mot sap xep to-po cua do thi (dung DFS) la:" << std::endl;
        for (int i = 0; i < topo_order.size(); ++i) {
            std::cout << topo_order[i] << (i == topo_order.size() - 1 ? "" : " -> ");
        }
        std::cout << std::endl;
    } else {
        std::cout << "Khong the tim thay sap xep to-po (do thi co chu trinh)." << std::endl;
    }

     // Ví dụ đồ thị có chu trình (thêm cạnh 5 -> 0)
    std::cout << "\nTest voi do thi co chu trinh (them canh 5 -> 0):" << std::endl;
    std::vector<std::vector<int>> adj_cycle = adj; // Sao chép đồ thị cũ
    adj_cycle[5].push_back(0); // Thêm cạnh 5 -> 0
    std::vector<int> topo_order_cycle = topologicalSortDFS(V, adj_cycle);

    if (!topo_order_cycle.empty()) {
         std::cout << "Mot sap xep to-po cua do thi co chu trinh (dung DFS) la:" << std::endl;
         for (int i = 0; i < topo_order_cycle.size(); ++i) {
             std::cout << topo_order_cycle[i] << (i == topo_order_cycle.size() - 1 ? "" : " -> ");
         }
         std::cout << std::endl;
    } else {
         std::cout << "Khong the tim thay sap xep to-po (do thi co chu trinh)." << std::endl;
    }


    return 0;
}

Giải thích code DFS:

std::vector<int> visited_state(V, 0): Mảng theo dõi trạng thái thăm của đỉnh. 0: chưa thăm, 1: đang thăm, 2: đã thăm xong.
std::list<int> result_list: Danh sách liên kết để xây dựng kết quả. Sử dụng std::list tiện lợi cho việc thêm phần tử vào đầu (push_front).
Hàm đệ quy dfs_visit(u, ...):
- Kiểm tra visited_state[u] == 1: Nếu đỉnh u đang ở trạng thái "đang thăm" (nghĩa là nó nằm trong stack đệ quy hiện tại) và chúng ta lại gặp nó, đó là một chu trình. Hàm trả về true để báo hiệu.
- Kiểm tra visited_state[u] == 2: Nếu đỉnh đã "thăm xong", nghĩa là nó và tất cả các đỉnh mà nó trỏ tới đã được xử lý và thêm vào kết quả, chúng ta chỉ cần dừng nhánh đệ quy này. Trả về false.
- visited_state[u] = 1: Đánh dấu đỉnh hiện tại là "đang thăm".
- Vòng lặp for (int v : adj[u]): Duyệt qua các hàng xóm v của u. Gọi đệ quy dfs_visit(v, ...). Nếu bất kỳ cuộc gọi đệ quy nào phát hiện chu trình, chúng ta cũng dừng và trả về true.
- visited_state[u] = 2: Sau khi đã duyệt hết tất cả các hàng xóm của u và đảm bảo không có chu trình từ u đi ra các nhánh đó, chúng ta đánh dấu u là "đã thăm xong".
- result_list.push_front(u): Quan trọng. Đỉnh u được thêm vào đầu danh sách kết quả. Điều này đảm bảo rằng u sẽ đứng trước tất cả các đỉnh mà nó trỏ tới (vì các đỉnh đó đã được thêm vào list sau khi cuộc gọi đệ quy đến chúng hoàn thành, và chúng ta đang thêm u vào trước chúng).
Hàm topologicalSortDFS: Duyệt qua tất cả các đỉnh để đảm bảo xử lý cả các thành phần liên thông không thể tiếp cận từ đỉnh 0. Nếu một đỉnh chưa thăm (state 0), gọi dfs_visit. Nếu dfs_visit trả về true (phát hiện chu trình), set cờ cycle_found và dừng vòng lặp.
Cuối cùng, kiểm tra cycle_found. Nếu có, báo lỗi và trả về vector rỗng. Nếu không, chuyển kết quả từ std::list sang std::vector và trả về.

So sánh hai thuật toán

Kahn:
- Ưu điểm: Dễ hiểu (dựa trên loại bỏ phụ thuộc), tự nhiên sử dụng hàng đợi, dễ dàng phát hiện chu trình bằng cách đếm số đỉnh đã xử lý.
- Nhược điểm: Cần tính toán bậc vào ban đầu.
DFS:
- Ưu điểm: Dễ triển khai đệ quy nếu quen thuộc với DFS, phát hiện chu trình ngay lập tức khi đi ngược lại một đỉnh đang thăm.
- Nhược điểm: Cần quản lý các trạng thái thăm (visited_state), kết quả cần được thêm vào đầu hoặc đảo ngược lại cuối cùng.

Cả hai thuật toán đều có độ phức tạp thời gian là O(V + E), trong đó V là số đỉnh và E là số cạnh, vì chúng ta cần duyệt qua tất cả các đỉnh và cạnh của đồ thị. Độ phức tạp không gian là O(V + E) để lưu trữ đồ thị và các cấu trúc dữ liệu phụ trợ (bậc vào, hàng đợi, stack đệ quy, trạng thái thăm).

Kết luận (Loại bỏ theo yêu cầu)

Ứng dụng thực tế sâu hơn

Để thấy rõ hơn sức mạnh của Sắp xếp tô-pô, hãy đi sâu vào một vài ứng dụng cụ thể:

1. Lập lịch Khóa học (Course Scheduling): Giả sử bạn có danh sách các môn học và các môn tiên quyết. Đây là một DAG hoàn hảo. Một cạnh từ "Cấu trúc dữ liệu" đến "Giải thuật" có nghĩa là bạn phải học "Cấu trúc dữ liệu" trước. Sắp xếp tô-pô cho phép bạn tạo ra một trình tự học các môn hợp lệ. Nếu có một chu trình (ví dụ: môn A là tiên quyết của B, B là tiên quyết của C, và C lại là tiên quyết của A), bạn không thể hoàn thành việc học!

Ví dụ: Môn học: Intro to CS, Data Structures, Algorithms, Calculus I, Linear Algebra. Phụ thuộc:

Intro to CS -> Data Structures
Data Structures -> Algorithms
Calculus I -> Linear Algebra

Đồ thị: Intro to CS (0) -> Data Structures (1) Data Structures (1) -> Algorithms (2) Calculus I (3) -> Linear Algebra (4) (Môn 5 - giả sử là History - không có phụ thuộc hoặc tiên quyết)

Áp dụng Sắp xếp tô-pô (ví dụ dùng Kahn): Bậc vào ban đầu: 0:0, 1:1, 2:1, 3:0, 4:1, 5:0 Queue: [0, 3, 5]

Lấy 0. Kết quả: [0]. in_degree[1] giảm -> 0. Queue: [3, 5, 1]
Lấy 3. Kết quả: [0, 3]. in_degree[4] giảm -> 0. Queue: [5, 1, 4]
Lấy 5. Kết quả: [0, 3, 5]. Queue: [1, 4]
Lấy 1. Kết quả: [0, 3, 5, 1]. in_degree[2] giảm -> 0. Queue: [4, 2]
Lấy 4. Kết quả: [0, 3, 5, 1, 4]. Queue: [2]
Lấy 2. Kết quả: [0, 3, 5, 1, 4, 2]. Queue: []

Một sắp xếp tô-pô hợp lệ: [Intro to CS, Calculus I, History, Data Structures, Linear Algebra, Algorithms]. Chú ý rằng thứ tự tương đối của các cặp phụ thuộc (Intro CS trước Data Structures, Data Structures trước Algorithms, Calculus I trước Linear Algebra) được bảo toàn. Các môn không phụ thuộc lẫn nhau (như History với các môn khác) có thể xuất hiện ở nhiều vị trí khác nhau trong sắp xếp tô-pô, miễn là không vi phạm các phụ thuộc.

2. Hệ thống Build (Build Systems): Khi bạn biên dịch một dự án phần mềm lớn, các file hoặc module thường phụ thuộc lẫn nhau. Một file header (.h) phải được xử lý trước các file nguồn (.cpp) sử dụng nó. Các thư viện phải được biên dịch trước chương trình chính. Sắp xếp tô-pô được sử dụng để xác định đúng thứ tự biên dịch các thành phần này. Make, CMake, Maven, Gradle... đều sử dụng nguyên lý này.

Ví dụ: File A.cpp include B.h, B.h include C.h. File D.cpp include B.h. Chương trình chính main.cpp cần A.o và D.o (object files sau biên dịch). Phụ thuộc: C.h -> B.h B.h -> A.cpp B.h -> D.cpp A.cpp -> A.o D.cpp -> D.o A.o -> main.cpp D.o -> main.cpp

Đồ thị (đơn giản hóa): C -> B B -> A B -> D A -> Main D -> Main

Sắp xếp tô-pô (ví dụ dùng DFS): Duyệt từ Main. dfs(Main): neighbors A, D. dfs(A): neighbor B. dfs(B): neighbor C. dfs(C): no neighbors. visited[C]=2. result_list.push_front(C). List: [C] B neighbors done. visited[B]=2. result_list.push_front(B). List: [B, C] A neighbors done. visited[A]=2. result_list.push_front(A). List: [A, B, C] dfs(D): neighbor B. B already visited (state 2). D neighbors done. visited[D]=2. result_list.push_front(D). List: [D, A, B, C] Main neighbors done. visited[Main]=2. result_list.push_front(Main). List: [Main, D, A, B, C]

Kết quả: [Main, D, A, B, C]. Đảo ngược lại: [C, B, A, D, Main]. Thứ tự này cho thấy C.h phải được xử lý đầu tiên, rồi đến B.h, sau đó A.cpp và D.cpp (có thể song song), cuối cùng là Main.cpp sử dụng A.o và D.o.

3. Lập lịch tác vụ với phụ thuộc (Task Scheduling): Trong các hệ thống quản lý dự án hoặc các quy trình tự động hóa, các tác vụ thường có phụ thuộc ("Tác vụ B không thể bắt đầu trước khi Tác vụ A hoàn thành"). Sắp xếp tô-pô giúp xác định một trình tự thực hiện các tác vụ sao cho tất cả các phụ thuộc được tôn trọng. Nếu có chu trình, tức là có một tập hợp các tác vụ phụ thuộc lẫn nhau một cách luẩn quẩn, thì không có cách nào hoàn thành tất cả chúng.

Ví dụ: Task 1: Gather requirements Task 2: Design Database (requires Task 1) Task 3: Develop API (requires Task 2) Task 4: Develop Frontend (requires Task 2) Task 5: Write Documentation (requires Task 3, Task 4)

Đồ thị: Task 1 -> Task 2 Task 2 -> Task 3 Task 2 -> Task 4 Task 3 -> Task 5 Task 4 -> Task 5

Sắp xếp tô-pô (ví dụ dùng Kahn): Bậc vào ban đầu: 1:0, 2:1, 3:1, 4:1, 5:2 Queue: [1]

Lấy 1. Kết quả: [1]. in_degree[2] giảm -> 0. Queue: [2]
Lấy 2. Kết quả: [1, 2]. in_degree[3] giảm -> 0, in_degree[4] giảm -> 0. Queue: [3, 4]
Lấy 3. Kết quả: [1, 2, 3]. in_degree[5] giảm -> 1. Queue: [4]
Lấy 4. Kết quả: [1, 2, 3, 4]. in_degree[5] giảm -> 0. Queue: [5]
Lấy 5. Kết quả: [1, 2, 3, 4, 5]. Queue: []

Sắp xếp tô-pô: [Task 1, Task 2, Task 3, Task 4, Task 5]. Trình tự này đảm bảo tất cả các phụ thuộc được thỏa mãn. Task 3 và Task 4 có thể thực hiện song song sau khi Task 2 hoàn thành.

Lưu ý về Sắp xếp tô-pô duy nhất

Một điều cần nhớ là một đồ thị có hướng không chu trình có thể có nhiều hơn một sắp xếp tô-pô. Điều này xảy ra khi có hai đỉnh u và v không có đường đi nào giữa chúng (không phụ thuộc lẫn nhau). Trong trường hợp đó, thứ tự tương đối giữa u và v trong sắp xếp tô-pô có thể khác nhau. Cả thuật toán Kahn và DFS đều có thể đưa ra các sắp xếp tô-pô khác nhau tùy thuộc vào thứ tự các đỉnh được xử lý khi có nhiều lựa chọn (ví dụ: thứ tự các đỉnh có bậc vào 0 trong hàng đợi của Kahn, hoặc thứ tự duyệt các hàng xóm trong DFS).

Tuy nhiên, điều quan trọng là tất cả các sắp xếp tô-pô hợp lệ đều tôn trọng các mối quan hệ phụ thuộc đã cho (u luôn trước v nếu có cạnh u -> v).

Bài tập ví dụ:

Đường đi trong trò chơi

Trong một buổi giải trí cuối tuần, FullHouse Dev đã tìm thấy một trò chơi thú vị. Trò chơi có nhiều màn chơi được kết nối với nhau bởi các cổng dịch chuyển một chiều. Nhiệm vụ của họ là tìm ra có bao nhiêu cách để di chuyển từ màn 1 đến màn cuối cùng.

Bài toán

Trò chơi có \(n\) màn chơi được kết nối bởi \(m\) cổng dịch chuyển một chiều. Các cổng được thiết kế sao cho không tạo thành chu trình có hướng trong đồ thị. Nhiệm vụ là tìm số cách có thể để hoàn thành trò chơi (di chuyển từ màn 1 đến màn \(n\)).

INPUT FORMAT:

Dòng đầu tiên chứa hai số nguyên \(n\) và \(m\): số lượng màn chơi và số lượng cổng dịch chuyển. Các màn chơi được đánh số từ 1 đến \(n\).
\(m\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(a\) và \(b\): mô tả một cổng dịch chuyển từ màn \(a\) đến màn \(b\).

OUTPUT FORMAT:

In ra một số nguyên: số cách có thể để hoàn thành trò chơi. Do kết quả có thể rất lớn, hãy in ra phần dư khi chia cho \(10^9+7\).

Ràng buộc:

\(1 \leq n \leq 10^5\)
\(1 \leq m \leq 2 \cdot 10^5\)
\(1 \leq a,b \leq n\)

Ví dụ

INPUT

OUTPUT

Giải thích

Có 3 cách để di chuyển từ màn 1 đến màn 4:

Cách 1: 1 → 2 → 4
Cách 2: 1 → 3 → 4
Cách 3: 1 → 4 (trực tiếp) Đây là hướng dẫn giải bài toán "Đường đi trong trò chơi" sử dụng C++ và các kiến thức về Cấu trúc dữ liệu và Giải thuật, cụ thể là Đồ thị và Quy hoạch động (Dynamic Programming) trên Đồ thị Không Chu trình Có Hướng (DAG - Directed Acyclic Graph).

Phân tích bài toán:

Đồ thị: Bài toán mô tả các màn chơi và cổng dịch chuyển một chiều, không tạo thành chu trình. Đây chính xác là một Đồ thị Không Chu trình Có Hướng (DAG). Các màn chơi là các đỉnh (nodes), các cổng dịch chuyển là các cạnh có hướng (directed edges).
Mục tiêu: Tìm số lượng đường đi distinct từ đỉnh 1 đến đỉnh n.
Kết quả: Số lượng đường đi có thể rất lớn, nên cần lấy phần dư khi chia cho 10^9 + 7.

Hướng giải:

Bài toán đếm số đường đi trên DAG là bài toán kinh điển có thể giải hiệu quả bằng Quy hoạch động.

Xây dựng mô hình:
- Sử dụng danh sách kề (adjacency list) để biểu diễn đồ thị. adj[u] sẽ chứa danh sách các đỉnh v mà có cổng dịch chuyển từ u đến v (cạnh u -> v).
- Vì DP cần tính toán dựa trên các đỉnh đi trước, ta cũng cần biết số lượng cạnh đi vào mỗi đỉnh (in-degree).
Quy hoạch động (Dynamic Programming):
- Định nghĩa trạng thái DP: Gọi dp[i] là số lượng đường đi distinct từ màn 1 đến màn i.
- Trạng thái cơ sở: dp[1] = 1 (Có 1 cách để đi từ màn 1 đến chính nó - đứng yên). dp[i] = 0 cho tất cả các màn i > 1 ban đầu.
- Công thức chuyển trạng thái: Để đến màn v, ta có thể đến từ bất kỳ màn u nào mà có cổng dịch chuyển u -> v. Số lượng đường đi đến v bằng tổng số lượng đường đi đến tất cả các màn u có cạnh u -> v. Tức là: dp[v] = sum(dp[u]) với mọi đỉnh u mà có cạnh u -> v.
- Thứ tự tính toán: Để tính dp[v], ta cần biết giá trị dp[u] cho tất cả các đỉnh u có cạnh đi vào v. Điều này có nghĩa là ta cần tính toán DP theo thứ tự sao cho mọi đỉnh u đi trước đỉnh v trong đồ thị đều được tính toán trước v. Thứ tự này chính là thứ tự Topo (Topological Sort) của đồ thị.
Thực hiện bằng Topo Sort và DP:
- Một cách hiệu quả để tính DP theo thứ tự Topo là sử dụng thuật toán Kahn's cho Topo Sort, kết hợp với DP.
- Khởi tạo mảng in_degree cho tất cả các đỉnh. Đếm số lượng cạnh đi vào mỗi đỉnh từ input.
- Khởi tạo mảng dp với dp[1] = 1 và dp[i] = 0 cho i > 1.
- Sử dụng một hàng đợi (queue) cho Topo Sort. Thêm vào hàng đợi tất cả các đỉnh có in_degree bằng 0.
- Trong khi hàng đợi chưa rỗng:
  - Lấy một đỉnh u từ đầu hàng đợi.
  - Đối với mỗi đỉnh v là hàng xóm của u (có cạnh u -> v):
    - Cập nhật dp[v] = (dp[v] + dp[u]) % (10^9 + 7). (Số đường đi đến u đóng góp vào số đường đi đến v).
    - Giảm in_degree[v] đi 1.
    - Nếu in_degree[v] trở thành 0, thêm v vào hàng đợi.
- Sau khi quá trình kết thúc, dp[n] sẽ chứa số lượng đường đi từ màn 1 đến màn n.
Lưu ý về Modulo:
- Thực hiện phép tính modulo 10^9 + 7 sau mỗi lần cộng vào mảng dp để tránh tràn số nguyên.

Các bước thực hiện chi tiết:

Đọc n và m.
Tạo danh sách kề adj (ví dụ: vector<vector<int>> adj(n + 1);).
Tạo mảng in_degree (ví dụ: vector<int> in_degree(n + 1, 0);).
Đọc m cạnh, với mỗi cạnh a -> b:
- Thêm b vào danh sách kề của a (adj[a].push_back(b);).
- Tăng in_degree[b] lên 1.
Tạo mảng dp (ví dụ: vector<long long> dp(n + 1, 0);). Đặt dp[1] = 1.
Tạo một hàng đợi (ví dụ: queue<int> q;).
Duyệt qua tất cả các đỉnh từ 1 đến n. Nếu in_degree[i] bằng 0, thêm i vào hàng đợi.
Thực hiện vòng lặp Topo Sort:
- while (!q.empty()) { ... }
- Lấy u = q.front(); q.pop();
- Nếu dp[u] == 0 (đỉnh u không thể đạt được từ đỉnh 1), bỏ qua việc lan truyền DP từ nó. (Mặc dù với cách khởi tạo dp[1]=1 và các đỉnh khác 0, điều này tự nhiên xảy ra).
- Duyệt qua các đỉnh v trong adj[u]:
  - dp[v] = (dp[v] + dp[u]) % 1000000007;
  - in_degree[v]--;
  - if (in_degree[v] == 0) q.push(v);
Kết quả là dp[n]. In ra giá trị này.

Ưu điểm của cách giải này:

Đảm bảo tính đúng đắn vì dựa trên nguyên lý quy hoạch động trên DAG.
Hiệu quả về thời gian: Độ phức tạp O(N + M) do mỗi đỉnh và mỗi cạnh được xử lý một số lượng lần hằng số.
Hiệu quả về không gian: Độ phức tạp O(N + M) để lưu trữ đồ thị, in-degree, và mảng DP.

Làm thêm nhiều bài tập miễn phí tại đây

Comments

There are no comments at the moment.