Có tên cho mẫu thiết kế "điều cần xử lý" không?

Question

Có một mẫu thiết kế tôi sử dụng một lần trong một thời gian và tôi không biết nó được gọi là gì. Có lẽ nó có một cái tên và ai đó ở đây biết điều đó?

Đó là điều tôi sử dụng khi tôi muốn đi qua một cấu trúc giống cây và thực hiện một số thao tác trên tất cả các nút của nó. Nó có dạng như sau:

nodes_to_handle = [root_node] 
while nodes_to_handle: 
    node = nodes_to_handle.pop() 
    # handle node 
    nodes_to_handle += node.get_neighbors() 

Lưu ý rằng cấu trúc không phải là cây; ví dụ, mẫu này có thể được sử dụng để làm tràn ngập trong một mảng.

Vì vậy, có tên được chấp nhận cho mẫu thiết kế này không?

Answer 1

Tôi nghĩ rằng những gì bạn đang đạt được là một mô hình tổng quát hơn so với độ sâu đầu tiên: danh sách biên giới. Danh sách biên giới là danh sách các phần tử được sắp xếp hoặc chưa được phân loại vẫn yêu cầu xử lý; thuật toán tiếp tục loại bỏ các phần tử và xử lý chúng cho đến khi danh sách rỗng hoặc một số tiêu chí chấm dứt khác được đáp ứng.

Ví dụ yêu thích của tôi về mẫu này là thuật toán của dijkstra. Trong Dijkstra's, danh sách biên giới là một hàng đợi ưu tiên hoặc đống, và phần tử có giá trị nhỏ nhất được bật ra khỏi heap mỗi lần lặp.

Answer 2

Điều này trông giống như thuật toán độ sâu đầu tiên theo chiều ngang. (Kể từ khi bạn bật danh sách từ cuối)

Nó có thể được thực hiện quát trong một vài cách khác nhau:

• Sử dụng một iterator mà đi qua cây (cách ưa thích)
• Sử dụng một hàm traversal (như của bạn) với một cuộc gọi lại (cho mã số #handle node).
  • Bên ngoài lớp nút
  • Bên trong lớp nút
• ...

Edit: Không nhìn vào mã đúng. :)

Answer 3

Đây là depth-first graph traversal. Đây là số algorithm, không phải là design pattern. (Từ bình luận của Jochen Ritzel.)