Изучение, понимание и внедрение структур данных и алгоритмов в Javascript для начинающего программиста сложно, но возможно.

Как кодер-самоучка, я сразу погрузился в создание проектов, следуя одному учебнику YouTube за другим. Это ускорило мой процесс обучения и позволило мне постепенно влюбиться в программирование. Структуры данных и алгоритмы меня не интересовали отдаленно — как программиста, который проектирует. До недавнего времени я поставил перед собой задачу потратить более 40 часов на LeetCode, решая задачи начального уровня.

Привет, это Вал. В этой статье я хотел бы поделиться некоторыми концепциями структур данных и алгоритмов в Javascript. Теперь давайте проверим поиск в глубину.

Где используется ДФС?

Поиск в глубину использует структуру данных стека для поиска кратчайшего пути на основе метода ребер. Для обнаружения циклов в графе путем проверки задних ребер. Чтобы решить лабиринты — головоломки с одним решением. Чтобы найти пути между двумя заданными узлами.

Что такое поиск в глубину?

Вот куча котов — больших и маленьких. Добавьте (прямого) котенка из (начального) кота в стек. Затем перейдите к первому внуку в очереди. Правнук и так далее. Теперь переходим к следующему непосещенному прямому котенку и продолжаем, пока снова не добавится каждый прямой котенок. В отличие от поиска в ширину — в первую очередь посещаются прямые котята, а не однопометники.

(Держу пари, что в 2032 году у них будут рюкзаки-переноски для кошек на солнечных батареях. Довольно круто!)

stack 
visitedCats 
while(!stack empty){
     cat = stack.top()
     stack.pop()
     for(kittens of cat){
          if(!visited){
               push into stack
               mark as visited
          }
     }
}

Поиск в глубину — один из 10 самых популярных алгоритмов, которые задают на собеседованиях по программированию. Вы можете найти множество простых практических задач здесь, на LeetCode. Удачного кодирования :)

Некоторые полезные ресурсы

Алгоритмы поиска по графам за 100 секунд — и дальше с помощью JS от Fireship

Графические алгоритмы для технических интервью — полный курс от freeCodeCamp