По мере того, как я продолжаю свое путешествие по разработке программного обеспечения, важность понимания алгоритмов становится все более и более актуальной. Работодатели хотят знать, что вы не просто запоминаете код, но понимаете основы лучших практик кодирования.
Обход графа — распространенный сценарий, с которым вы столкнетесь при работе с большими группами данных. Граф — это нелинейная структура данных, содержащая узлы и ребра. Узел (также известный как вершина) — это единственное уникальное значение в графе, а ребро представляет собой отношение между этими двумя узлами.
Подумайте о приложении для социальных сетей. Пользователь — это узел, и когда пользователь следует за другим пользователем, это создает границу (отношение) между двумя узлами. Теперь подумайте о том, насколько большим является приложение, такое как Facebook или Twitter, и только представьте, какой массивный график он создает! Это подчеркивает важность графиков и возможность их правильного перемещения.
Что ж… графики и их отношения могут иногда сбивать с толку, как мы можем их визуализировать?
Матрица смежности:
Матрица смежности — это, по сути, таблица, которая представляет количество ребер между двумя узлами. Как мы видим ниже, A к A не имеет ребер, потому что A не соединяется сам с собой, однако B к A имеет соединение, поэтому мы ставим 1 в столбце, то же самое касается C to A и так далее.
Это отличный способ визуализировать небольшой график, подобный приведенному выше, но на более крупном графике мы можем видеть гораздо больше нулей, чем единиц, что без всякой причины занимает много места. Для таких сценариев мы будем использовать список смежности.
Список смежности:
список смежности сокращает пробелы и напрямую определяет, какие узлы связаны друг с другом. Как я уже говорил, часто это лучший способ визуализировать граф и его ребра, не имея большого количества пустого пространства.
На изображении выше у нас есть список смежности слева. Этот список представляет соединения между узлами. A соединяется с обоими B и C, B соединяется с A, и так на.
Теперь у нас есть твердое фундаментальное понимание графов, но как нам правильно их перемещать? Что, если мы хотим знать, соединится ли узел A в конечном итоге с узлом D без этого визуального представления? Приходят алгоритмы!!
Поиск в ширину:
Поиск в ширину (или сокращенно BFS) — это стратегия обхода графа, которая ищет граф по одному уровню за раз, вот наглядный пример:
Из начального узла (уровень 0) мы добавляем в очередь всех прямых потомков (уровень 1). После того, как эти узлы были посещены, перейдите к следующему набору дочерних элементов (уровень 2) и так далее. Обратите внимание: важно отметить, какие узлы были посещены, поскольку вы не хотите посещать один и тот же узел дважды.
Еще один вариант обхода графа — поиск в глубину.
Поиск в глубину:
Эта стратегия обхода графа является рекурсивным алгоритмом, который включает возврат. В этом сценарии откат означает, что вы продвигаетесь вперед (узел за узлом), пока не останется узлов для посещения. Если больше нет узлов для посещения, алгоритм вернется на один узел и проверит, есть ли другой путь для следования. Если есть путь, по которому нужно следовать, он следует по этому пути до тех пор, пока не останется узлов для поиска, таким образом, цикл повторяется.
Это может показаться немного запутанным, но я объясню! Выше у нас тот же граф, который мы прошли с помощью алгоритма поиска в ширину, только на этот раз мы используем алгоритм поиска в глубину.
Шаг 1: Начиная сверху (A), мы посещаем первый дочерний узел (B)
Шаг 2. Теперь в B мы переходим к первому дочернему узлу B (E)
Шаг 3: Если E не соответствует критериям, которые мы ищем, и поскольку ниже него больше нет дочерних узлов, в конечном итоге мы должны вернуться к родительскому узлу (B), чтобы проверить, есть ли у него другие дочерние элементы.
Шаг 4. У B есть еще один дочерний элемент (F)! Затем мы посещаем этот узел. Если этот узел соответствует нашим критериям, то вуаля! Алгоритм решен! НО, если он не соответствует нашим критериям, мы возвращаемся к родителю (B) и проверяем, есть ли у него еще дочерние элементы и так далее.
Этот цикл повторяется до тех пор, пока не будет найден искомый узел.
Теперь вам может быть интересно, оба эти алгоритма довольно эффективны при поиске узлов, какой из них выбрать?
Представьте себе, что в приведенном выше примере мы сначала переходим к узлу B, а не к узлу C или D, но что, если узел который мы ищем, является узлом D, простым дочерним элементом узла A. Это означает, что мы будем искать узел B и все его дочерние элементы, затем узел C и все его дочерние элементы, а затем, НАКОНЕЦ, перейдем к узлу D. Это означает, что наш алгоритм потратил целую кучу времени на поиск других участков графика, когда ответ был прямо перед нашими глазами!
В конечном счете, именно по этой причине люди отдают предпочтение алгоритму поиска в ширину, а не поиску в глубину. Я не говорю, что DFS никогда не следует использовать, но это может оказаться пустой тратой времени.
Я надеюсь, что вы нашли эту статью полезной для получения дополнительной информации о BFS и DFS!
Если вы хотите увидеть, как я реализую алгоритмы DFS и BFS с помощью JavaScript, ознакомьтесь с моей второй статьей здесь!
