Sắp xếp tô pô cho chuỗi học phần tiên quyết

1. Quy ước chiều cạnh

Đặt cạnh từ học phần tiên quyết tới học phần phụ thuộc. Học phần có bậc vào bằng 0 có thể xuất hiện tiếp theo. Sau khi chọn một học phần, giảm bậc vào của mọi môn phụ thuộc trực tiếp. Khi nhiều học phần cùng sẵn sàng, dùng mã tăng dần để kết quả dễ lặp lại khi dữ liệu đầu vào đổi thứ tự.

2. Giữ bất biến của thuật toán

Bậc vào còn lại của mỗi môn đếm số tiên quyết chưa được đưa ra. Một môn chỉ được vào hàng đợi khi số đếm giảm về 0. Nếu hàng đợi rỗng nhưng vẫn còn môn, đồ thị còn lại có chu trình. Các môn chưa xử lý có thể gồm cả môn nằm sau chu trình, nên danh sách còn lại chưa phải là danh sách chính xác các đỉnh nằm trên chu trình.

3. Tái hiện với đồ thị nhỏ

A và B đứng trước C, C đứng trước D. Hai thứ tự bắt đầu A hoặc B đều hợp lệ. Hàng đợi ưu tiên chọn A trước B. Thêm cạnh D → A để tạo chu trình và kiểm tra thuật toán báo lỗi. Với hàng đợi ưu tiên, chi phí là O(E + V log V) khi mỗi đỉnh vào hàng đợi đúng một lần.

Chạy ví dụ bằng python gt_topo_hoc_phan.py.

from heapq import heapify, heappush, heappop

def thu_tu(hoc_phan, canh):
    bac = dict.fromkeys(hoc_phan, 0)
    ke = {mon: [] for mon in bac}
    for truoc, sau in canh:
        ke[truoc].append(sau)
        bac[sau] += 1
    cho = [mon for mon in bac if bac[mon] == 0]
    heapify(cho)
    ket_qua = []
    while cho:
        mon = heappop(cho)
        ket_qua.append(mon)
        for sau in ke[mon]:
            bac[sau] -= 1
            if bac[sau] == 0:
                heappush(cho, sau)
    if len(ket_qua) != len(bac):
        raise ValueError("Có chu trình tiên quyết")
    return ket_qua

canh = [("A", "C"), ("B", "C"), ("C", "D")]
assert thu_tu("DCBA", canh) == list("ABCD")
try:
    thu_tu("ABCD", canh + [("D", "A")])
except ValueError:
    print("ABCD hợp lệ. Thêm D → A tạo chu trình.")
else:
    raise AssertionError("Phải phát hiện chu trình")

4. Phân biệt thứ tự và kế hoạch học kỳ

Một thứ tự hợp lệ chưa xác định học kỳ tối ưu, vì còn giới hạn tín chỉ, học phần chỉ mở theo kỳ và có thể có đồng tiên quyết. Hãy bổ sung lớp quy tắc hoặc mô hình tối ưu sau khi xác nhận đồ thị hợp lệ. So tập cạnh đã nhập với đề cương đào tạo trước khi kết luận chu trình là lỗi của chương trình.

Đọc thêm Tài liệu giải thuật của Princeton.