Sắp xếp tô pô
Mỗi lần bạn cài phần mềm, build một chương trình hay lên kế hoạch cho một dự án, phải có thứ gì đó xác định việc nào làm trước. Nếu công việc B cần công việc A, thì A phải làm sớm hơn. Sắp xếp tô pô biến một mạng lưới các quy tắc như vậy thành một đường thẳng.
Ý tưởng
Vẽ mỗi công việc thành một đỉnh và mỗi quy tắc "A trước B" thành một mũi tên từ A đến B. Thứ tự tô pô là một hàng gồm tất cả các đỉnh, trong đó mọi mũi tên đều chỉ sang phải. Nó được gọi là sắp xếp vì nó đặt mọi thứ theo thứ tự, nhưng khác với sắp xếp số, nó chỉ cần tôn trọng các mũi tên: những đỉnh không được nối bởi chuỗi mũi tên nào có thể đứng theo thứ tự bất kỳ.
Khi nào không thể
Nếu các mũi tên tạo thành chu trình, chẳng hạn A trước B, B trước C và C trước A, thì A sẽ phải đứng trước chính nó. Vì vậy thứ tự tô pô tồn tại khi và chỉ khi đồ thị không có chu trình có hướng. Một đồ thị như vậy gọi là đồ thị có hướng không chu trình, hay DAG. Cả hai phương pháp dưới đây đều tìm ra chu trình nếu có, nên chúng cũng là cách kiểm tra chu trình tiện lợi.
Một ví dụ
Lấy các mũi tên A → C, B → C, B → D, C → E và D → E. Thuật toán Kahn đếm mũi tên đi vào: A và B không có, nên A đứng đầu, rồi đến B. Bỏ các mũi tên của B làm C và D tự do, chúng đứng tiếp theo, rồi đến E: thứ tự A, B, C, D, E. Phương pháp DFS thăm A, rồi C, rồi E; E xong trước, rồi C, rồi A, mỗi đỉnh được xếp lên đầu. Sau đó nó thăm B và D, chúng xong và đứng trước các đỉnh kia: thứ tự B, D, A, C, E. Cả hai thứ tự đều đúng.
Kahn hay DFS?
Thuật toán Kahn, được Arthur Kahn công bố năm 1962, đi theo chiều xuôi: nó luôn biết công việc nào có thể bắt đầu ngay, hợp với việc lập lịch, và có thể chọn giữa các công việc tự do theo quy tắc bất kỳ, chẳng hạn thứ tự chữ cái. Phương pháp DFS, được Robert Tarjan phổ biến năm 1976, đi ngược từ các điểm cuối và chỉ cần một lần tìm kiếm theo chiều sâu. Thời gian của cả hai đều tăng theo số đỉnh cộng số cạnh.
Ứng dụng
Các công cụ build như make biên dịch một tệp sau những tệp mà nó phụ thuộc. Trình quản lý gói cài thư viện theo thứ tự phụ thuộc. Bảng tính tính lại một ô sau các ô mà công thức của nó dùng đến. Trường đại học kiểm tra xem các môn tiên quyết có thể đáp ứng không, trình biên dịch sắp xếp lệnh, và các pipeline dữ liệu chạy mỗi bước sau khi đầu vào của nó đã sẵn sàng. Lệnh Unix tsort tự nó thực hiện một phép sắp xếp tô pô.
Khám phá
Mở ứng dụng và nhấn Bước. Các mũi tên cho biết đỉnh nào phải đứng trước đỉnh nào. Với thuật toán Kahn, số trên mỗi đỉnh đếm số mũi tên đi vào còn lại, và các đỉnh tự do có màu xanh dương. Với phương pháp DFS, đỉnh xanh dương là đang thăm và đỉnh xanh lá là đã xếp. Thứ tự dài dần ở hàng dưới đồ thị. Đánh dấu Thêm chu trình và xem cả hai phương pháp phát hiện rằng không có thứ tự nào.
Câu hỏi thường gặp
Tô pô ở đây nghĩa là gì?
Cái tên đến từ tô pô học, ngành nghiên cứu cách các thứ được nối với nhau thay vì hình dạng chính xác của chúng. Thứ tự chỉ phụ thuộc vào việc đỉnh nào được nối bằng mũi tên, chứ không phụ thuộc vào chỗ chúng được vẽ.
Khi không có thứ tự, làm sao tìm ra chu trình?
Phương pháp DFS cho thấy ngay: cạnh tới một đỉnh vẫn đang thăm, cùng với đường đi gồm các đỉnh đang thăm, chính là chu trình. Thuật toán Kahn chỉ cho biết đỉnh nào bị kẹt; tìm kiếm trong số các đỉnh đó sẽ ra chu trình.
Tôi có thể chọn một thứ tự cụ thể trong số các thứ tự hợp lệ không?
Có. Trong thuật toán Kahn, khi có nhiều đỉnh tự do, hãy chọn đỉnh bạn muốn, ví dụ nhãn nhỏ nhất hoặc công việc gấp nhất. Dùng hàng đợi ưu tiên sẽ cho thứ tự đứng đầu theo bảng chữ cái.
Sắp xếp tô pô được dùng với đường đi ngắn nhất thế nào?
Trên đồ thị có hướng không chu trình, nới lỏng các cạnh của từng đỉnh theo thứ tự tô pô sẽ tìm được mọi đường đi ngắn nhất từ một điểm xuất phát chỉ trong một lượt, kể cả khi có cạnh âm, nhanh hơn Dijkstra hay Bellman–Ford.
Sẵn sàng thử chưa?
Mở PictorX trong trình duyệt — không cần cài đặt, không cần thẻ tín dụng để bắt đầu.
Thử sắp xếp tô pô