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

Tính toán thứ tự sắp xếp topo của một đồ thị có hướng không chu trình (DAG) bằng thuật toán Kahn hoặc DFS. Hỗ trợ phát hiện chu trình, báo cáo đường đi chu trình, xây dựng chế độ xem lớp thực thi song song, hỗ trợ thứ tự từ điển nhỏ nhất và mô phỏng từng bước trên đồ thị tương tác.

⚡ Thử ví dụ:

Chuỗi tuyến tính Thứ tự mặc đồ Môn học tiên quyết Thói quen buổi sáng Mục tiêu Build Mẫu danh sách kề Có chu trình Pipeline DAG

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

→ Danh sách cạnh

⧇ Danh sách kề

Dữ liệu đồ thị

Định dạng cạnh: A -> B (cũng chấp nhận →, =>, :). Tối đa 80 đỉnh / 800 cạnh.

Định dạng kề: A: B, C, D — mỗi đỉnh một dòng, theo sau là các đỉnh kế tiếp trực tiếp.

Thuật toán

Thuật toán Kahn (từ điển) cho thứ tự duy nhất, có thể tái lập. DFS post-order là phương pháp duyệt theo chiều sâu cổ điển.

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

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.

Định nghĩa thứ tự topo

Một hoán vị (v₁, v₂, …, v_n) của V là topo nếu và chỉ nếu
với mọi cạnh (u → v) trong E: vị trí(u) < vị trí(v)

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.

Thuật toán Kahn (mã giả)

Kahn(G):
  Q ← { v ∈ V : bậc_vào(v) = 0 }
  L ← [ ]
  trong khi Q không trống:
    u ← Q.pop()
    L.append(u)
    với mỗi cạnh u → v:
      bậc_vào(v) -= 1
      nếu bậc_vào(v) = 0: Q.push(v)
  nếu |L| < |V|: báo cáo chu trình
  khác: trả về L

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|).

DFS post-order (mã giả)

DFS-Topo(G):
  với mỗi đỉnh u trong V: màu[u] ← TRẮNG
  L ← ngăn xếp rỗng
  với mỗi đỉnh u trong V:
    nếu màu[u] = TRẮNG: visit(u)
  trả về đảo_ngược(L)

visit(u):
  màu[u] ← XÁM
  với mỗi cạnh u → v:
    nếu màu[v] = XÁM: báo cáo chu trình
    nếu màu[v] = TRẮNG: visit(v)
  màu[u] ← ĐEN; L.push(u)

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.

A -> B, B -> C, A -> C
C -> D
Ao_so_mi -> Ca_vat -> Ao_khoac

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:.

A: B, C
B: D
C: D
D:

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

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.
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.).
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.
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.
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

Tham khảo nội dung, trang hoặc công cụ này như sau:

"Máy Tính Sắp Xếp Topo" tại https://MiniWebtool.com/vi/may-tinh-sap-xep-topo/ từ MiniWebtool, https://MiniWebtool.com/

bởi đội ngũ miniwebtool. Cập nhật: 20 Tháng 4, 2026

Bạn cũng có thể thử AI Giải Toán GPT của chúng tôi để giải quyết các vấn đề toán học của bạn thông qua câu hỏi và trả lời bằng ngôn ngữ tự nhiên.

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

Máy Tính Ma Trận KềMới

Máy tính Đường đi Ngắn nhất Dijkstra

Máy Tính Tô Màu Đồ ThịMới

Trình xác thực dãy bậc đồ thị

Công cụ Kiểm tra Đường đi HamiltonMới

Công cụ giải phương trình tuyến tính

Công cụ Giải Quy hoạch Tuyến tínhMới

Máy Tính Ma Trận

Máy Tính Nhân Ma TrậnMới

Máy Tính Luồng Mạng (Luồng Cực Đại)Mới

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

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

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

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

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

DFS post-order (Tarjan, 1976)

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

Phát hiện chu trình

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

Danh sách cạnh

Danh sách kề

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

Ứng dụng trong thực tế

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Đọc thêm

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

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

Công cụ nổi bật: