В этом посте будет рассмотрена довольно простая задача AlgoExpert — «Поиск в глубину».

В этом посте будет рассмотрена довольно простая задача AlgoExpert — «Поиск в глубину».

На первый взгляд я принял это за BST-задачу поиска в глубину, но, к счастью, перед тем, как начать, я заметил, что это обход дерева.

Деревья интересны мне тем, что они не так просты, как бинарные деревья, и все же почему-то они кажутся более интуитивно понятными в работе. Хотя это может быть потому, что я обычно использую рекурсию в бинарных деревьях и итерацию в деревьях.

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

Подумав

Так почему именно стек помогает мне пройти через это?

Давайте рассмотрим это шаг за шагом.

Я начинаю с корня («А»), поэтому добавлю его дочерние элементы в стек.

Теперь я перейду к следующему узлу, вытащив его из стека.

А теперь добавьте его дочерние элементы в стек.

Теперь я зайду и в «Е», и в «F» — их тоже лопну.

Отсюда достаточно легко увидеть, чем это заканчивается и почему стек так хорошо подходит для поиска в глубину. Процесс LIFO (последний пришел, первый ушел) естественным образом отдает приоритет глубине.

Реализация:

В AlgoExpert нам будет предоставлен класс Node для реализации метода DFS.

Вместо того, чтобы разбивать этот процесс на части, я просто дам свое полное решение (оно очень простое и понятное).

Массив, который мы возвращаем (как указано в задаче), будет включать все имена узлов в правильном порядке в глубину.

И это все для этого!

Хотя это относительно простая задача, мне все же нравится тратить время на то, чтобы укрепить применение метода. Простые обходы лежат в основе многих других, более сложных задач, и хорошо разбираться в них кажется отличной идеей.

Дополнительные материалы на PlainEnglish.io. Подпишитесь на нашу бесплатную еженедельную рассылку. Подпишитесь на нас в Twitter, LinkedIn, и Discord .