- Hiện tại
- Tự do hoặc đang thăm
- Đã xếp
- Chu trình
Sắp xếp tô pô
Tất trước giày, móng trước tường, một môn học trước môn cần đến nó. Sắp xếp tô pô xếp các đỉnh của một đồ thị có cạnh một chiều thành một hàng, trong đó mọi cạnh đều hướng về phía sau. Chọn thuật toán Kahn hoặc phương pháp DFS rồi đi từng bước để xem thứ tự dài dần, và thêm một chu trình để thấy vì sao khi đó không thể có thứ tự nào. Nhấn Phát để xem thứ tự dài dần, hoặc dùng Bước và Lùi để đi từng bước. Kéo thanh trượt bước để nhảy đến bất kỳ đâu. Mỗi cạnh là một chiều, như mũi tên cho thấy: hãy hiểu nó là "cái này đứng trước cái kia". Chọn phương pháp: thuật toán Kahn xếp các đỉnh không có cạnh đi vào trước, và số trên mỗi đỉnh là số cạnh đi vào nó còn lại; phương pháp DFS xếp mỗi đỉnh lên đầu khi mọi thứ đứng sau nó đã được xếp. Hàng dưới đồ thị là thứ tự đến lúc đó. Đánh dấu Thêm chu trình để xem mỗi phương pháp tìm ra chu trình thế nào. Đồ thị mới tạo một đồ thị khác; chọn số đỉnh và số cạnh. Khi bảng đang được chọn, phím mũi tên đi từng bước, phím cách phát và tạm dừng, còn Home và End nhảy về đầu và cuối.
Cách nó hoạt động
- Chọn thuật toán Kahn hoặc phương pháp DFS.
- Nhấn Phát, hoặc dùng Bước và Lùi để đi từng bước. Kéo thanh trượt bước để nhảy đến bất kỳ đâu.
- Theo dõi thứ tự dài dần dưới đồ thị. Đánh dấu Thêm chu trình để xem mỗi phương pháp tìm ra chu trình thế nào.
Thuật toán Kahn
Với mỗi đỉnh, đếm xem có bao nhiêu cạnh trỏ tới nó. Một đỉnh không có cạnh nào trỏ tới thì không phụ thuộc vào gì, nên có thể đứng đầu. Xếp một đỉnh như vậy, rồi bỏ các cạnh đi ra từ nó: các đỉnh mà chúng trỏ tới giờ bớt một cạnh đi vào, và một số có thể về 0 và trở nên tự do. Cứ xếp các đỉnh tự do cho đến khi không còn đỉnh nào. Nếu có đỉnh không bao giờ được tự do, chúng đang chờ nhau trong một chu trình, và không tồn tại thứ tự tô pô.
Phương pháp DFS
Chạy tìm kiếm theo chiều sâu từ mỗi đỉnh chưa thăm. Một đỉnh xong khi mọi thứ đến được từ nó đã xong, nên mọi thứ phải đứng sau nó đều đã được xếp. Đặt mỗi đỉnh đã xong lên đầu thứ tự, và thứ tự thu được sẽ đúng. Nếu quá trình tìm kiếm đi theo một cạnh tới một đỉnh mà nó vẫn đang ở bên trong, cạnh đó khép một chu trình, và một lần nữa không có thứ tự nào.
Câu hỏi thường gặp
Sắp xếp tô pô là gì?
Một cách sắp xếp các đỉnh của đồ thị có hướng trong đó mọi cạnh đều đi từ đỉnh đứng trước tới đỉnh đứng sau. Nếu cạnh có nghĩa là "phải đứng trước", đó là một thứ tự để làm được mọi công việc.
Khi nào tồn tại thứ tự tô pô?
Khi và chỉ khi đồ thị không có chu trình có hướng: nó là đồ thị có hướng không chu trình, hay DAG. Nếu có chu trình, mọi đỉnh trên đó sẽ phải đứng trước chính nó.
Thứ tự tô pô có duy nhất không?
Thường là không. Khi hai đỉnh không được nối bởi một chuỗi cạnh, đỉnh nào đứng trước cũng được, nên một đồ thị có thể có nhiều thứ tự hợp lệ. Thuật toán Kahn và phương pháp DFS thường cho ra các thứ tự khác nhau.
Sắp xếp tô pô nhanh đến đâu?
Cả hai phương pháp đều xem mỗi đỉnh và mỗi cạnh một số lần cố định, nên khối lượng công việc tăng theo số đỉnh cộng số cạnh.
Đồ thị của tôi có bị gửi đi đâu không?
Không. Đồ thị được tạo và sắp xếp ngay trong trình duyệt của bạn, và cài đặt gần nhất được lưu trong bộ nhớ cục bộ của trình duyệt này.
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.
Tới trình chỉnh sửa