Topological Sort

Sắp xếp topo

Trên đồ thị có hướng không có chu trình G(V,E) một thứ tự Tôpô của G là một danh sách của tất cả các đỉnh trên đồ thị G, sao cho với bất cứ hai đỉnh u,v  trên G mà có cạnh nối từ u đến v thì u phải đứng trước v trong danh sách.

Để tìm Topo ta có thể sử dụng:

  • Thuật toán tìm kiếm theo chiều sâu (DFS): Các đỉnh kết thúc thăm sau cùng sẽ nằm đầu trong danh sách topo. Ta thực hiện DFS với các đỉnh trên G, sau đó đưa ra các đỉnh theo thứ tự giảm dần về thời gian kết thúc thăm. Ở đây thay vì việc dùng tem thời gian (Time Stamp) ta dùng stack cài đặt bằng danh sách liên kết để lưu trữ các đỉnh có thời gian thăm sau cùng trước.
  • Thuật toán tìm kiếm theo chiều rộng (BFS): Các đỉnh mà không có cạnh vào (bậc vào bằng 0) là đỉnh sẽ nằm đầu trong danh sách topo. Ta thực hiện việc tìm kiếm các bậc vào của các đỉnh, nếu đỉnh nào có bậc vào bằng 0 thì ta đưa đỉnh đó vào trong danh sách topo, và loại bỏ các cạnh nối từ đỉnh đó đến các đỉnh khác (giảm bậc vào của các đỉnh mà có cạnh nối từ đỉnh đó). Lặp lại việc tìm kiếm đỉnh có bậc vào bằng 0, cho đến khi tất cả các đỉnh được thăm hết.

http://www.mediafire.com/?ia2oi50rctabo5c

2 Responses to Topological Sort

  1. Tuấn Nguyễn Thanh nói:

    Thưa thầy

    Thầy cho em hỏi một chút ạ.

    Nếu duyệt đồ thị trên đề tìm topo thì duyệt bằng 2 phương pháp DFS và BFS mỗi phương pháp lại ra một kết quả khác nhau, như vậy cho chính xác không ạ . Hay là duyệt bằng phương pháp nào thì cũng phải đưa ra cùng kết quả ạ.
    Vì em thấy duyệt đồ thì bằng DFS thì có trường hợp không duyệt được hết các đỉnh

  2. thdcbkhn nói:

    Trên một đồ thì có thể có nhiều topological!
    Trong DFS nếu còn đỉnh chưa duyệt thì ta lại bắt đầu duyệt tiếp từ đỉnh đó, sau đó đưa ra các đỉnh theo thứ tự giảm thời điểm kết thúc thăm.

Gửi phản hồi

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s

%d bloggers like this: