Поиск в глубину и в ширину — алгоритмы DFS и BFS

Попробуйте нашу полную платформу: https://nas.io/backtobackswe 📹 Интуитивно понятные видеообъяснения ❓ Новые, ранее не встречавшиеся вопросы 🔎 Получите все решения DFS и BFS — это не просто алгоритмы поиска по графу. Это фундаментальный метод поиска связей определённым образом и посещения узлов любого типа в желаемом порядке. Эти связи могут быть представлены в виде графа, или мы можем проверять расстояние между символами одной строки и другой, ИЛИ мы можем обходить дерево определённым образом. Это концепции поиска, а не только концепции графов. Реализация DFS может выполняться итеративно с использованием стека или рекурсивно, поскольку стек вызовов будет служить стеком для запоминания точек возврата. Структура стека может заменить наши стековые кадры из рекурсии, поэтому DFS может быть написан рекурсивно, благодаря принципу «последний вошел — первый вышел» (LIFO) в порядке обработки узлов. Поиск в ширину (BFS) выполняется итеративно. Он использует очередь с порядком обработки «первым вошел — первым вышел». Примеры использования Поиск в ширину (DFS) хорош для таких задач, как возврат назад, доступ к листовым узлам в дереве или для всего, где мы хотим в первую очередь углубляться в путь и исчерпать все возможности, прежде чем вернуться. Поиск в ширину лучше подходит для таких задач, как определение существования пути между узлами, поскольку он отдает приоритет ширине поиска, а не глубине (отсюда «поиск в ширину»), а также для определения расстояния или «уровней», на которые один узел находится от другого. Метод 1.) Выберите структуру данных в зависимости от поиска. 2.) Добавьте начальный узел. 3.) Удалите узел из структуры данных. 4.) Если узел не был обнаружен: 4a.) Отметьте его как обнаруженный в наборе «обнаруженных». 4b.) Выполните работу над узлом. 5.) Для каждого из дочерних элементов 5a.) Если дочерний элемент не был обнаружен (не обработан) 5ai.) Добавьте дочерний элемент в структуру данных. Повторяйте, пока структура данных не пуста. Временная сложность Если отношения представлены списком смежности, то: Время: O(V + E) Пространство: O(V)* Где V — общее количество посещенных вершин (или узлов), а E — общее количество пройденных ребер. *Хотя условия могут меняться. Нас интересует только МАКСИМАЛЬНОЕ количество узлов в структуре данных одновременно. Если мы выполняем DFS на сбалансированном дереве, пространственная сложность будет O(h), где h — высота дерева, поскольку в стеке будет находиться путь длиной максимум h узлов. То же самое относится и к обходу дерева в порядке уровней. Пространство будет ограничено МАКСИМАЛЬНОЙ ШИРИНОЙ дерева, поскольку мы будем хранить в очереди максимум определенное количество узлов одновременно. И так далее... все зависит от ситуации, спросите у интервьюера, какой анализ ему нужен: наихудший, средний или наилучший. «Список смежности» означает, что каждый узел хранит своих смежных соседей в списке. ++++++++++++++++++++++++++++++++++++++++++++++++++++ HackerRank:    / @hackerrankofficial   Tuschar Roy:    / tusharroy2525   GeeksForGeeks:    / @geeksforgeeksvideos   Jarvis Johnson:    / vsympathyv   Success In Tech:    / @successintech