В ширину по сравнению с глубиной сначала

Question

В ширину по сравнению с глубиной сначала

Вы можете предоставить Comparator в методе sort в качестве второго параметра:

Arrays.sort(f, Comparator.comparing(Flight::getFlight_number));

Comparable интерфейс на самом деле не обязателен.

166

algorithm depth-first-search breadth-first-search tree-traversal

задан Matthijs Wessels 2 February 2014 в 23:45

1 ответ

Другие вопросы по тегам:

algorithm depth-first-search breadth-first-search tree-traversal

Похожие вопросы:

score 278 · Accepted Answer

Эти два условия дифференцируются между двумя различными способами обойти дерево.

Является, вероятно, самым легким только показать различие. Рассмотрите дерево:

    A
   / \
  B   C
 /   / \
D   E   F

Глубина первый обход посетила бы узлы в этом порядке

A, B, D, C, E, F

Заметьте, что Вы идете полностью вниз один участок перед хождением дальше.

Обход вершин в ширину посетил бы узел в этом порядке

A, B, C, D, E, F

Здесь мы работаем полностью через каждый уровень перед потерей работоспособности.

(Обратите внимание, что существует некоторая неоднозначность в пересекающихся заказах, и я обманул для поддержания порядка "чтения" на каждом уровне дерева. Или в случае я мог добраться до B прежде или в после C, и аналогично я мог добраться до E прежде или после F. Это может или не может иметь значения, зависит от Вас приложение...),

Оба вида обхода могут быть достигнуты с псевдокодом:

Store the root node in Container
While (there are nodes in Container)
   N = Get the "next" node from Container
   Store all the children of N in Container
   Do some work on N

Различие между двумя пересекающимися заказами заключается в выборе Container.

Поскольку глубина сначала использует стек. (Рекурсивная реализация использует стек вызовов...),
Для использования в ширину очередь.

Рекурсивная реализация похожа

ProcessNode(Node)
   Work on the payload Node
   Foreach child of Node
      ProcessNode(child)
   /* Alternate time to work on the payload Node (see below) */

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

На данном этапе я все еще обманул немного. С небольшим умом можно также работать - над узлами в этом порядке:

D, B, E, F, C, A

который является изменением в глубину, где я не делаю работы над каждым узлом, пока я не иду, создают резервную копию дерева. Я однако посетил более высокие узлы на пути вниз для нахождения их детей.

Этот обход является довольно естественным в рекурсивной реализации (используйте "Альтернативное время" строка выше вместо первой строки "Работы"), и не слишком трудно, если Вы используете явный стек, но я оставлю его как осуществление.