Trong hệ thống quản lý kho hàng thương mại điện tử, các sản phẩm có quan hệ phụ thuộc để lắp ráp. Làm thế nào để áp dụng thuật toán Kahn dựa trên cấu trúc In-degree để phát hiện các vòng lặp phụ thuộc không hợp lệ trong đồ thị có hướng (Directed Acyclic Graph)?

Question

Accepted Answer

Bản chất vấn đề
Trong bài toán chuỗi cung ứng hoặc lắp ráp sản phẩm, một số linh kiện phải được hoàn thành trước khi linh kiện khác bắt đầu. Điều này tạo ra một đồ thị có hướng. Nếu sơ đồ phụ thuộc chứa chu trình (ví dụ: Linh kiện A phụ thuộc vào B, B phụ thuộc vào C, và C lại phụ thuộc vào A), hệ thống sẽ rơi vào trạng thái khóa chết (Deadlock) và không thể lập lịch sản xuất.
Thuật toán Kahn là một phương pháp kinh điển để giải quyết bài toán Sắp xếp Topo (Topological Sort) dựa trên khái niệm bậc vào (In-degree - số lượng cạnh đi vào một đỉnh).
Cơ chế hoạt động của thuật toán Kahn

Tính In-degree cho tất cả các đỉnh trong đồ thị.
Đưa tất cả các đỉnh có In-degree bằng 0 vào một Queue (vì đây là các công việc không có phụ thuộc, có thể thực hiện ngay).
Lần lượt lấy một đỉnh ra khỏi Queue, thêm vào danh sách kết quả, sau đó giảm In-degree đi 1 của tất cả các đỉnh kề với nó.
Nếu sau khi giảm, đỉnh kề nào có In-degree về 0, đưa đỉnh đó vào Queue.
Sau khi kết thúc, nếu số lượng đỉnh được xử lý bằng tổng số đỉnh của đồ thị thì đồ thị là DAG (hợp lệ). Ngược lại, nếu số lượng đỉnh xử lý ít hơn tổng số đỉnh, tức là tồn tại chu trình (Circular Dependency).

Ví dụ minh họa (JavaScript / Node.js)
function checkCircularDependency(numNodes, edges) {
    const inDegree = new Array(numNodes).fill(0);
    const adjList = Array.from({ length: numNodes }, () => []);

// Xây dựng đồ thị và tính In-degree
    for (let [u, v] of edges) {
        adjList[u].push(v);
        inDegree[v]++;
    }

const queue = [];
    for (let i = 0; i < numNodes; i++) {
        if (inDegree[i] === 0) {
            queue.push(i);
        }
    }

let processedCount = 0;
    while (queue.length > 0) {
        const curr = queue.shift();
        processedCount++;

for (let neighbor of adjList[curr]) {
            inDegree[neighbor]--;
            if (inDegree[neighbor] === 0) {
                queue.push(neighbor);
            }
        }
    }

// Nếu processedCount nhỏ hơn numNodes nghĩa là có chu trình
    return processedCount !== numNodes;
}
Lưu ý kinh nghiệm thực chiến

Thuật toán Kahn rất trực quan và dễ cài đặt cho các lập trình viên Junior khi cần validate dữ liệu cấu hình hoặc phân quyền dạng cây có liên thông chéo.
Trong môi trường Enterprise, việc phát hiện chu trình phụ thuộc nên được thực hiện ngay tại tầng API Validation khi người dùng cập nhật cấu hình để tránh lỗi Runtime.

Bản chất vấn đề

Làm Chủ Phỏng Vấn & Nâng Cao Trình Độ Chuyên Nghiệp

Tải Tuyển Tập 100+ Câu Hỏi Phỏng Vấn Chuyên Sâu (PDF)

Cần Mentor Phỏng Vấn Thử 1-1 & Tối Ưu CV?

Kiểm Tra CV Chuẩn ATS Miễn Phí

Câu hỏi graph theory liên quan cùng chủ đề