Два графических алгоритма, которые должен знать каждый разработчик!

В век данных алгоритмы обхода графов являются одними из наиболее применимых инструментов для инженеров-программистов. Обход графа - это процесс поиска некоторого пути в сети или просто исследование сети определенным образом. Существуют десятки алгоритмов и стратегий обхода графа - поиск в ширину (BFS) и поиск в глубину (DFS) оказались простыми, но очень эффективными алгоритмами для решения задач графа.

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

Понять алгоритмы

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

Начиная с основ, сеть графов может иметь бесконечное количество размеров и конфигураций. В этой статье основное внимание будет уделено графам в формате дерева, где есть один корневой узел с множеством дочерних узлов.

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

Каждый уровень дерева определяется глубиной иерархии дочерних элементов. Этой информации должно быть более чем достаточно, чтобы понять графики в контексте этой статьи.

Теперь по алгоритмам!

Поиск в глубину (DFS) исследует график глубоко, а не широко. Когда дело доходит до понимания теории графов, визуализация является ключевым моментом. Если изображение стоит тысячи слов, то гифка - много.

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

Поиск в ширину (BFS) позволяет исследовать график широко, а не глубоко. В то время как DFS пытается добраться до конечных точек графа как можно быстрее, BFS будет исследовать граф по слоям. Выбор между DFS и BFS зависит от контекста, они оба одинаково полезны по-своему.

Реализация на Go

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

На собеседованиях по программированию часто просят выполнить DFS или BFS на таком дереве. В подобном вопросе обычно требуется вернуть массив, который состоит из значений узлов в графе, размещенных в порядке, соответствующем используемому нами алгоритму. Вот примеры возвращаемых значений для нас:

DFS: [1,2,5,9,10,6,3,4,7,8]

BFS: [1,2,3,4,5,6,7,8,9,10]

Поиск в глубину на ходу

Для DFS действительно не так много кода. Я не буду включать код для построения дерева в эту статью, но если вы действительно хотели бы это увидеть, оставьте комментарий ниже, и я добавлю его! Вернемся к нашему примеру, наш тип данных Node имеет два свойства Value и массив узлов, представляющих его дочерние элементы.

Наша функция DepthFirstSearch() работает с переданной структурой узла, принимая ее в качестве аргумента-предшественника (n *Node). Затем мы передаем массив, который будет содержать значения массива в порядке нашего метода обхода. DFS прост в том, что мы просто немедленно вызываем DFS для дочерних узлов каждого узла.

Примечание. Это не рекурсивный алгоритм! Мы просто вызываем DFS на каждом дочернем узле, который мы распаковываем с предыдущего узла. Мы используем ключевое слово range для перебора дочерних узлов и отбрасываем первый аргумент с _, потому что это просто индекс, который нам не важен.

Поиск в ширину в Go

BFS немного сложнее, чем DFS, но ненамного! Основное отличие состоит в том, что вместо того, чтобы сразу переходить к следующему найденному дочернему элементу, мы хотим добавить значения каждого дочернего элемента для одного узла, прежде чем перейти к следующему слою.

Мы делаем это, используя queue, который мы инициализируем в строке 7 как массив, в котором хранятся ссылки на узлы, начиная с одной структуры. Затем мы запускаем цикл for, который продолжается до тех пор, пока в очереди есть элементы. Поскольку queue представляет порядок узлов, которые нам осталось пройти, мы знаем, что будем исследовать весь граф, как только queue станет пустым.

Внешний цикл for представляет уровень графа, на котором мы находимся. Итак, мы сначала инициализируем наш текущий узел первым элементом очереди в строке 9. Затем мы «выталкиваем» нашу очередь, используя нарезку массива в Go. Это делается тем, что нам нужен первый элемент и все, что следует за ним, то есть queue[1:].

Затем мы добавляем текущее значение, которое мы только что прошли, к массиву возвращаемых значений. Последний шаг - добавить всех дочерних узлов этого узла к нашему queue, что мы и делаем, снова используя ключевое слово range над дочерними элементами узла.

В заключение, основное различие между DFS и BFS заключается в том, что DFS немедленно переходит к следующему дочернему элементу, в то время как DFS будет исследовать граф по уровням через очередь.

Надеюсь, вам понравилась эта статья. Если вы хотите добавить дополнительную информацию или узнать о другом алгоритме, оставьте комментарий ниже! Спасибо за прочтение.