Topological sort

Là một thuật toán dùng để sắp xếp các đỉnh của một đồ thị có hướng không chứa chu trình (DAG) thành một thứ tự tuyến tính sao cho với mỗi cạnh từ đỉnh A đến đỉnh B, đỉnh A luôn đứng trước đỉnh B trong thứ tự đó

Đặc điểm chính:

Chỉ áp dụng cho đồ thị có hướng không có chu trình (DAG)

Nếu đồ thị có chu trình, không thể thực hiện topological sort

Thứ tự sắp xếp

Nếu có đường đi từ đỉnh A → đỉnh B thì A phải đứng trước B trong thứ tự kết quả

Không duy nhất

Một đồ thị có thể có nhiều hơn một thứ tự sắp xếp topo hợp lệ

Ứng dụng

Xác định thứ tự thực hiện các công việc có ràng buộc trước-sau (ví dụ: thứ tự học các môn có môn tiên quyết, biên dịch mã nguồn, lập lịch công việc, v.v.)

Kiểm tra chu trình

Nếu không thể sắp xếp topo, đồ thị có chứa chu trình

Cách hoạt động (nguyên lý)

Có hai cách phổ biến để thực hiện topological sort:

Duyệt theo chiều sâu (DFS): Duyệt DFS, khi kết thúc duyệt một đỉnh thì thêm vào stack. Kết quả là thứ tự ngược lại của thứ tự lấy đỉnh ra khỏi stack

Thuật toán Kahn (BFS): Lần lượt xóa các đỉnh có in-degree bằng 0, cập nhật lại in-degree của các đỉnh kề. Cách này cũng trả về một thứ tự hợp lệ

Example: Dry run Topological Sort

Đầu vào (Input):

Đồ thị có hướng không chu trình (DAG) dưới dạng danh sách kề:

A → B, A → C

B → D

C → D

Biểu diễn dưới dạng code:

graph_example = { 'A': ['B', 'C'], 'B': ['D'], 'C': ['D'], 'D': [] }

Hình minh họa:

A | \ v v B C \/ v D

Chạy từng bước

Tính in-degree (số cạnh vào) của từng đỉnh:

A: 0

B: 1 (từ A)

C: 1 (từ A)

D: 2 (từ B và C)

Khởi tạo hàng đợi với các đỉnh có in-degree = 0:

Hàng đợi ban đầu: [A]

Lặp:

Lấy A khỏi hàng đợi, thêm vào kết quả: ['A']

Giảm in-degree của B và C xuống 0 → Thêm B và C vào hàng đợi: [B, C]

Lấy B khỏi hàng đợi, thêm vào kết quả: ['A', 'B']

Giảm in-degree của D xuống 1 (vì B → D)

Lấy C khỏi hàng đợi, thêm vào kết quả: ['A', 'B', 'C']

Giảm in-degree của D xuống 0 (vì C → D) → Thêm D vào hàng đợi: [D]

Lấy D khỏi hàng đợi, thêm vào kết quả: ['A', 'B', 'C', 'D']

Kết quả cuối cùng:

['A', 'B', 'C', 'D']

Output

Một thứ tự topo hợp lệ:

['A', 'B', 'C', 'D']

Thứ tự này đảm bảo mọi đỉnh đều đứng trước các đỉnh mà nó trỏ tới, đúng theo ràng buộc của topological sort.

Loading content...

Topological sort