Thực tế Sử dụng Traversal Cấp bậc

Question

Ai đó có thể đề nghị tôi khi nào tôi cần một Traversal Cấp bậc (để giải quyết một số kịch bản thực tế/thực tế)?

Answer 1

Level order traversal thực sự là một Tìm kiếm đầu tiên rộng, không phải là đệ quy theo bản chất.

Từ: tìm kiếm http://en.wikipedia.org/wiki/Breadth-first_search

Breadth-đầu tiên có thể được sử dụng để giải quyết nhiều vấn đề trong lý thuyết đồ thị, ví dụ:

• Tìm tất cả các nút trong vòng một thành phần kết nối
• sao chép Collection, thuật toán của Cheney
• Tìm đường đi ngắn nhất giữa hai nút u và - v (với chiều dài đường dẫn được đo bằng số cạnh)
• Tes ting một đồ thị cho bipartiteness
• (Reverse) Cuthill-McKee lưới đánh số
phương pháp
• Ford-Fulkerson để tính toán dòng chảy tối đa trong một luồng trên mạng
• serialization/Deserialization của một cây nhị phân vs serialization trong trật tự sắp xếp, cho phép cây được xây dựng lại theo cách hiệu quả.

Answer 2

Hướng bản đồ của Google đang sử dụng Tra chuyển đơn hàng cấp (BFS) mọi lúc.

Thuật toán lặp lại cùng một phương pháp chọn nút gần điểm giao nhau nhất, cuối cùng chọn tuyến đường có độ dài ngắn nhất.

http://blog.hackerearth.com/breadth-first-search-algorithm-example-working-of-gps-navigation