Изучение, понимание и внедрение структур данных и алгоритмов в 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