Есть ли название в шаблоне «вещи для обработки»?

Question

Иногда я использую шаблон дизайна, и я не знаю, как он называется.Возможно, у него есть имя, и кто-то здесь его знает?

Это то, что я использую, когда хочу пройтись по древовидной структуре и выполнить некоторые действия на всех ее узлах.Это выглядит примерно так:

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

Обратите внимание, что структура не обязательно должна быть деревом;например, этот шаблон можно использовать для заливки массива.

Итак, есть ли приемлемое имя для этого шаблона проектирования?

Answer 1

Я думаю, что вы получаете более общую модель, чем обход в глубину: список границ. Граничный список - это (отсортированный или несортированный) список элементов, которые все еще требуют обработки; алгоритм продолжает удалять элементы и обрабатывать их до тех пор, пока список не станет пустым или не будут выполнены другие критерии завершения.

Мой любимый пример этого паттерна - алгоритм Дейкстры. В Dijkstra's список границ является приоритетной очередью или кучей, и элемент с наименьшим значением отбрасывается из кучи каждую итерацию.

Answer 2

Это похоже на алгоритм обхода в глубину . (так как вы выводите список с конца)

Это может быть реализовано в общем виде несколькими различными способами:

• Использование итератора, который пересекает дерево (предпочтительный способ)
• Использование функции обхода (например, вашей) с обратным вызовом (для кода #handle node).
  • За пределами класса узла
  • Внутри класса узла
• ...

Редактировать: неправильно смотрел код. :)

Answer 3

Это обход графика в глубину . Это алгоритм , а не шаблон проектирования . (Из комментария Йохена Ритцеля.)