Máy Tính Sắp Xếp Topo

Giới thiệu về Máy Tính Sắp Xếp Topo

Máy tính Sắp xếp Topo tính toán một cách sắp xếp tuyến tính các đỉnh của một đồ thị có hướng không chu trình (DAG) sao cho mọi cạnh có hướng từ u đến v đều đặt u trước v. Nhập đồ thị của bạn dưới dạng danh sách cạnh hoặc danh sách kề và công cụ sẽ trả về thứ tự topo bằng thuật toán Kahn hoặc DFS post-order, phát hiện các chu trình (với đường đi chu trình chính xác), nhóm các tác vụ thành các lớp thực thi song song, đếm số lượng các cách sắp xếp hợp lệ và minh họa từng bước trên một đồ thị tương tác.

Sắp xếp topo là gì?

Cho một đồ thị có hướng G = (V, E), một sắp xếp topo (hoặc thứ tự topo) là một sự sắp xếp tuyến tính v₁, v₂, …, vₙ của các đỉnh sao cho đối với mọi cạnh có hướng (u → v), u luôn xuất hiện trước v trong sự sắp xếp đó. Thứ tự topo tồn tại khi và chỉ khi đồ thị không có chu trình có hướng — nghĩa là đồ thị đó là một DAG. Thứ tự sắp xếp hiếm khi là duy nhất: một đồ thị có thể có nhiều cách sắp xếp topo hợp lệ khi có nhiều đỉnh cùng lúc có bậc vào bằng không.

Các thuật toán được sử dụng

Thuật toán Kahn (dựa trên BFS, 1962)

Thuật toán Kahn là phương pháp sắp xếp topo trực quan nhất. Tại mỗi bước, nó chọn một đỉnh có bậc vào bằng không (không có cạnh hướng vào), thêm nó vào kết quả và "loại bỏ" nó khỏi đồ thị bằng cách giảm bậc vào của từng đỉnh kế tiếp của nó. Khi có nhiều đỉnh có bậc vào bằng không, việc phân xử có thể sử dụng min-heap (cho thứ tự nhỏ nhất về mặt từ điển) hoặc hàng đợi FIFO (cho thứ tự chèn). Thuật toán Kahn chạy trong thời gian O(|V| + |E|) và kiêm luôn chức năng phát hiện chu trình: nếu bất kỳ đỉnh nào vẫn còn bậc vào > 0 sau khi hàng đợi trống, đồ thị đó có chu trình.

DFS post-order (Tarjan, 1976)

Thuật toán DFS chạy tìm kiếm theo chiều sâu, và bất cứ khi nào một đỉnh kết thúc (nghĩa là tất cả các đỉnh kế tiếp của nó đã được khám phá hết), nó sẽ được đẩy vào một ngăn xếp. Đảo ngược ngăn xếp ở cuối quá trình sẽ cho một thứ tự topo hợp lệ. Việc phát hiện chu trình rất tự nhiên: gặp một đỉnh vẫn đang trong quá trình khám phá (được đánh dấu XÁM) có nghĩa là đã tìm thấy một cạnh ngược, vì vậy đồ thị không phải là một DAG. DFS post-order cũng chạy trong thời gian O(|V| + |E|).

Các lớp thực thi song song

Chế độ xem phân lớp của một DAG chia các đỉnh của nó thành các cấp độ sao cho mọi cạnh đều đi từ cấp độ có số thấp hơn sang cấp độ cao hơn. Các đỉnh trong cùng một lớp độc lập với nhau, vì vậy chúng có thể được thực hiện song song. Số lượng các lớp bằng độ dài của đường đi dài nhất cộng một — đây là đường đi tới hạn của DAG, số vòng tuần tự tối thiểu cần thiết để hoàn thành tất cả các nhiệm vụ ngay cả khi có khả năng song song vô hạn. Máy tính này tự động tạo ra chế độ xem lớp bất cứ khi nào đầu vào là một DAG.

Phát hiện chu trình

Nếu đồ thị chứa một chu trình có hướng, không thể thực hiện sắp xếp topo. Máy tính của chúng tôi báo cáo đường đi chính xác của chu trình (ví dụ: A → B → C → A) và làm nổi bật các cạnh chu trình bằng màu đỏ trên hình minh họa. Việc loại bỏ bất kỳ cạnh đơn lẻ nào trong chu trình là đủ để khôi phục tính không chu trình.

Định dạng đầu vào

Danh sách cạnh

Viết mỗi cạnh có hướng dưới dạng nguồn -> đích, cách nhau bởi dấu phẩy hoặc dòng mới. Các biến thể mũi tên được chấp nhận: ->, →, =>, -->, :. Bạn cũng có thể viết chuỗi các cạnh: A -> B -> C là cách viết tắt của A->B và B->C. Nhãn đỉnh có thể là chữ cái, chữ số, dấu gạch dưới, dấu gạch ngang và dấu chấm.

Danh sách kề

Viết mỗi đỉnh, một dấu hai chấm và các đỉnh kế tiếp trực tiếp của nó (các đỉnh mà nó trỏ tới). Một đỉnh không có đỉnh kế tiếp vẫn cần dòng của nó, chẳng hạn như D:.

Cách sử dụng máy tính này

1. Chọn một định dạng: Chuyển đổi giữa danh sách cạnh và danh sách kề bằng các nút radio.
2. Nhập đồ thị: Dán dữ liệu của bạn hoặc nhấp vào một trong các ví dụ nhanh (thứ tự mặc đồ, môn học tiên quyết, mục tiêu build, đồ thị có chu trình, v.v.).
3. Chọn một thuật toán: Kahn từ điển cho thứ tự duy nhất, có thể tái lập; thứ tự chèn để giữ nguyên thứ tự nhập; DFS post-order cho phương pháp duyệt theo chiều sâu cổ điển; hoặc Hiển thị tất cả để xem mọi thứ tự cạnh nhau.
4. Nhấp vào "Sắp xếp Topo": Thứ tự sắp xếp, phát hiện chu trình, chế độ xem lớp, độ dài đường đi tới hạn, tổng số cách sắp xếp hợp lệ và đồ thị tương tác sẽ xuất hiện bên dưới.
5. Khám phá: Nhấn Play để xem từng đỉnh được xuất ra từng bước một. Các nhãn bậc vào cập nhật trực tiếp. Kéo bất kỳ nút nào để sắp xếp lại bố cục.

Ứng dụng trong thực tế

Hệ thống Build và trình biên dịch

Các công cụ như make, Bazel, Gradle và npm sắp xếp topo các mục tiêu build của chúng để mỗi mục tiêu chỉ được biên dịch sau khi tất cả các phụ thuộc của nó đã xong. Một chu trình trong đồ thị phụ thuộc thường được báo cáo là một lỗi nghiêm trọng — hệ thống build không thể quyết định bắt đầu từ đâu.

Lập lịch công việc

Các nhà quản lý dự án sử dụng DAG để nắm bắt các phụ thuộc của nhiệm vụ. Sắp xếp topo đưa ra một thứ tự thực hiện hợp lệ và chế độ xem lớp đưa ra số vòng tối thiểu khi có khả năng song song vô hạn. Chuỗi dài nhất là đường đi tới hạn quyết định thời gian thực hiện dự án.

Lập kế hoạch môn học tiên quyết

Danh mục khóa học của một trường đại học là một DAG: các cạnh là mối quan hệ tiên quyết. Một thứ tự topo là một kế hoạch học tập hợp lệ, và các lớp cho sinh viên biết những bộ môn nào họ có thể học song song trong mỗi học kỳ.

Tính toán lại bảng tính

Khi một ô thay đổi, bảng tính phải tính toán lại mọi ô hạ nguồn theo thứ tự phụ thuộc — một sắp xếp topo của DAG phụ thuộc giữa các ô. Các tham chiếu vòng (chu trình) sẽ bị ứng dụng từ chối.

Trình quản lý gói và trình tải plugin

Apt, pip, Homebrew, Maven và vô số khung làm việc plugin giải quyết thứ tự cài đặt hoặc tải bằng cách sắp xếp topo các DAG phụ thuộc của chúng.

Giải quyết biểu tượng và lập lịch chỉ thị

Trình biên dịch sử dụng sắp xếp topo để sắp xếp các khai báo, và CPU sử dụng DAG phụ thuộc dữ liệu để lập lịch các chỉ thị trong bộ đệm sắp xếp lại mà không vi phạm các nguy cơ dữ liệu.

Đếm số cách sắp xếp topo

Đối với một DAG có n đỉnh, số lượng các thứ tự topo hợp lệ khác nhau có thể dao động từ 1 (đối với một chuỗi được sắp xếp hoàn toàn) đến n! (đối với đồ thị không có cạnh). Việc tính toán số lượng chính xác nói chung là bài toán #P-complete, nhưng đối với các đồ thị có tối đa 16 đỉnh, máy tính này sẽ liệt kê chúng bằng cách sử dụng công thức quy hoạch động bitmask: f(S) = Σ f(S ∪ {v}) với mọi v ∉ S mà tất cả các đỉnh tiền nhiệm của nó đều nằm trong S.

Độ phức tạp và hiệu suất

• Thời gian: Cả thuật toán Kahn và DFS post-order đều chạy trong O(|V| + |E|) — tuyến tính theo kích thước của đồ thị.
• Không gian: O(|V|) để theo dõi bậc vào và thứ tự đầu ra, cộng với O(|V| + |E|) cho cấu trúc danh sách kề.
• Phát hiện chu trình: Được tích hợp sẵn trong cả hai thuật toán. Kahn phát hiện chu trình khi |đầu_ra| < |V|; DFS phát hiện chúng khi tìm thấy một cạnh ngược (hàng xóm XÁM).
• Giới hạn trong công cụ này: tối đa 80 đỉnh và 800 cạnh cho minh họa tương tác. Đếm số thứ tự giới hạn ở 16 đỉnh.

Câu hỏi thường gặp

Sắp xếp topo là gì?

Sắp xếp topo của một đồ thị có hướng không chu trình là một cách sắp xếp tuyến tính các đỉnh của nó sao cho mọi cạnh có hướng từ u đến v đều đặt u trước v. Nó đại diện cho một thứ tự hợp lệ để xử lý các nhiệm vụ tôn trọng các phụ thuộc của chúng.

Máy tính này sử dụng thuật toán nào?

Máy tính chạy cả thuật toán Kahn và DFS post-order. Thuật toán Kahn lặp lại việc loại bỏ một đỉnh có bậc vào bằng không và giảm bậc vào của các đỉnh kế tiếp của nó. DFS post-order chạy tìm kiếm theo chiều sâu và đảo ngược thứ tự kết thúc. Cả hai đều chạy trong thời gian O(|V| + |E|).

Điều gì xảy ra nếu đồ thị của tôi có chu trình?

Một đồ thị có chu trình có hướng sẽ không có sắp xếp topo. Máy tính sẽ phát hiện chu trình, làm nổi bật nó bằng màu đỏ trên hình minh họa và báo cáo đường đi chính xác của chu trình để bạn có thể biết cần loại bỏ cạnh nào để biến đồ thị thành một DAG.

Thứ tự topo nhỏ nhất về mặt từ điển là gì?

Khi có nhiều thứ tự topo hợp lệ, thứ tự nhỏ nhất về mặt từ điển đạt được bằng cách luôn chọn đỉnh nhỏ nhất theo bảng chữ cái có bậc vào bằng không tại mỗi bước. Chế độ Kahn mặc định của máy tính này trả về thứ tự duy nhất này, ổn định và dễ tái lập.

Chế độ xem lớp hoặc cấp độ là gì?

Chế độ xem lớp nhóm các đỉnh theo độ dài đường đi dài nhất từ bất kỳ nguồn nào. Các đỉnh trong cùng một lớp không có sự phụ thuộc lẫn nhau, vì vậy chúng có thể thực thi song song. Số lượng lớp bằng độ dài chuỗi phụ thuộc dài nhất cộng một và cho biết số vòng song song tối thiểu cần thiết để hoàn thành tất cả các tác vụ.

Một đồ thị có thể có nhiều thứ tự topo hợp lệ không?

Có. Nếu tại bất kỳ bước nào thuật toán Kahn có nhiều đỉnh với bậc vào bằng không, bất kỳ đỉnh nào trong số đó đều có thể được chọn tiếp theo. Máy tính này đếm số lượng chính xác các cách sắp xếp topo khác nhau cho các đồ thị có tối đa 16 đỉnh.

Sự khác biệt giữa thuật toán Kahn và DFS post-order là gì?

Kahn hoạt động theo kiểu top-down (từ trên xuống): nó liên tục chọn các nguồn (bậc vào 0) và xuất chúng trước. DFS post-order hoạt động theo kiểu bottom-up (từ dưới lên): nó hoàn thành các đỉnh đích trước và thêm chúng vào phía trước của thứ tự sắp xếp. Cả hai đều là O(|V| + |E|) và tạo ra các thứ tự topo hợp lệ, nhưng thường là các thứ tự khác nhau. Kahn dễ song song hóa và thích ứng cho thứ tự từ điển hơn; DFS dễ kết hợp với các phân tích dựa trên DFS khác như các thành phần liên thông mạnh.

Kích thước đồ thị tối đa mà công cụ này hỗ trợ là bao nhiêu?

Máy tính hỗ trợ tối đa 80 đỉnh và 800 cạnh. Việc đếm tổng số thứ tự topo hợp lệ được giới hạn ở 16 đỉnh vì bài toán là #P-complete và không gian trạng thái tăng theo 2ⁿ. Minh họa tương tác và hoạt ảnh thuật toán mở rộng mượt mà cho đến kích thước tối đa.

Đọc thêm

• Topological sorting — Wikipedia
• Directed acyclic graph — Wikipedia
• Depth-first search — Wikipedia
• Critical path method — Wikipedia
• Strongly connected component — Wikipedia

Các công cụ liên quan khác:

Phép toán toán học nâng cao:

• Máy Tính Antilog
• Máy tính hàm Beta
• Máy tính hệ số nhị thức
• Máy tính phân phối xác suất nhị thức
• Máy tính Bitwise
• Máy tính Định lý Giới hạn Trung tâm
• Máy tính kết hợp
• Máy tính hàm lỗi bổ sung
• Máy tính số phức
• Máy tính Entropy
• Máy tính chức năng lỗi
• Máy tính giảm dần theo cấp số nhân
• Máy tính tăng trưởng theo cấp số nhân
• Máy tính Tích phân Lũy thừa
• máy-tính-số-mũ-độ-chính-xác-cao Nổi bật
• Máy tính giai thừa Nổi bật
• Máy tính Hàm Gamma
• Máy tính tỷ lệ vàng
• Máy tính Nửa đời
• Máy tính phần trăm tăng trưởng
• Máy tính hoán vị
• Máy tính Phân phối Poisson
• Máy tính căn bậc của đa thức với các bước chi tiết
• Máy tính xác suất
• Máy tính phân bố xác suất
• Máy tính Tỷ lệ
• Máy tính công thức bậc hai
• Máy Tính Khoa Học Nổi bật
• Máy tính ký hiệu khoa học
• Máy Tính Chữ Số Có Nghĩa Mới
• Máy tính tổng khối
• Máy tính tổng các số liên tiếp
• Máy tính Tổng Bình phương
• Công cụ tạo bảng chân trị Mới
• Máy tính lý thuyết tập hợp Mới
• Công cụ tạo Biểu đồ Venn (3 Tập hợp) Mới
• Máy tính Định lý Số dư Trung Quốc Mới
• Máy tính Hàm Phi Euler Mới
• Máy tính Thuật toán Euclid Mở rộng Mới
• Máy tính Nghịch đảo Nhân theo Mô-đun Mới
• Máy tính Phân số liên tục Mới
• Máy tính Đường đi Ngắn nhất Dijkstra Mới
• Máy tính Cây khung nhỏ nhất Mới
• Trình xác thực dãy bậc đồ thị Mới
• Máy tính Hoán vị lệch (Giai thừa phụ) Mới
• Máy tính số Stirling Mới
• Máy tính Nguyên lý Chuồng bồ câu Mới
• Máy tính Phân phối Dừng Chuỗi Markov Mới
• Máy Tính Làm Tròn Mới
• Máy Tính Phân Phối Nhị Thức Âm Mới
• Máy tính Hoán vị Có lặp Mới
• Máy Tính Lũy Thừa Modular Mới
• Máy Tính Căn Nguyên Thủy Mới
• Công Cụ Rút Gọn Đại Số Boolean Mới
• Công cụ Giải Bản đồ Karnaugh (K-Map) Mới
• Máy Tính Tô Màu Đồ Thị Mới
• Máy Tính Sắp Xếp Topo Mới
• Máy Tính Ma Trận Kề Mới
• Máy tính Bao hàm - Loại trừ Mới
• Công cụ Giải Quy hoạch Tuyến tính Mới
• Trình Giải Bài Toán Người Du Hành (TSP) Mới
• Công cụ Kiểm tra Đường đi Hamilton Mới