Графики: поиск в ширину vs. поиск в глубину

Графики: поиск в ширину vs. поиск в глубину

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

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

Массивы и хэши могут использоваться для создания структур данных, отличных от классов, предоставленных нам в Ruby, таких как связанные списки, деревья и графики. В этом сообщении блога мы сосредоточимся на графиках. Мы рассмотрим, как правильно представить граф в Ruby, и два наиболее распространенных алгоритма поиска по графу: поиск в ширину и поиск в глубину.

Графическое представление

Проще говоря, граф в информатике - это набор связанных элементов. Мы называем эти элементы узлами или вершинами, и они соединяются ребрами. Например, в Facebook два пользователя будут представлены вершиной, а их статус дружбы будет представлен ребром. Это соединение позволяет использовать такие функции, как «Люди, которых вы можете знать», и видеть общих друзей с другими пользователями.

В графе слева вершинами будут: A, B, C, D, E и F.

Ребрами будут все линии, которые вы видите, соединяющие вершины: A-B, A-C, A-D, B-C, B-E, D-E, D-F.

Это легко увидеть в таком визуальном представлении, но как мы можем представить этот граф программно? Вершины можно хранить в массиве:

vertices = ['A', 'B', 'C', 'D', 'E']

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

Ребра также могут быть сохранены в массиве, но на этот раз мы будем использовать массив массивов:

edges = [
    ['A', 'B'], ['A', 'C'], ['A', 'D'], ['B', 'C'], ['B', 'E'],
    ['D', 'E'], ['D', 'F']
]

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

Введите поиск в ширину и поиск в глубину, два самых популярных алгоритма обхода графиков. Википедия дает следующее определение обхода графа в информатике:

В информатике обход графа (также известный как поиск графа) относится к процессу посещения (проверки и / или обновления) каждой вершины в графе . Такие обходы классифицируются по порядку посещения вершин.

Каждый из них представляет собой другой подход к обходу или посещению каждой вершины графа.

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

BFS относится к методу, в котором вы просматриваете граф, посещая всех дочерних узлов узла, прежде чем переходить к дочерним элементам этого дочернего узла. Вы можете мыслить уровнями. Если корневым узлом является уровень 1, вы посещаете все уровни 2, затем все уровни 3, все уровни 4 и т. Д. И т. Д.

В приведенном выше графе, имея корневой узел 1, мы начнем с узла, помеченного 1. Узел 1 будет считаться «посещенным», и затем мы посетим каждого из дочерних узлов узла 1, которыми будут узел 2 и узел 5. Теперь, когда мы посетили всех дочерних узлов узла 1, узел 1 будет считаться «исследованным», а узлы 2 и 5 будут считаться «посещенными». Затем мы посетим непосещенных потомков узла 2, которыми здесь будет узел 3. Теперь узел 2 исследуется, а узел 3 посещается.

Вместо того, чтобы обращаться к дочерним элементам узла 3, мы вернемся к узлу 5 и посетим детей узла 5. Опять же, мы посещаем каждый «уровень» перед тем, как двигаться дальше, и здесь 2 и 5 находятся на одном уровне. Итак, мы посещаем Узел 4 и отмечаем Узел 5 как исследованный.

Теперь мы возвращаемся к Узлу 3, чтобы посетить его непосещенные дочерние элементы, но у него нет ни одного, поэтому мы отмечаем его исследованным и возвращаемся к Узлу 4. Мы находим единственный дочерний узел узла 4, Узел 6, отмечаем его как посещенный и отмечаем Узел 4 как исследованный. . Затем мы видим, что у узла 6 нет дочерних узлов, и больше не осталось других непосещенных вершин для исследования, поэтому мы отмечаем узел 6 как исследованный, и наш алгоритм завершается.

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

Поиск в глубину

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

Используя тот же граф, что и выше, и имея корневой узел 1, мы снова начнем с узла, помеченного 1, и посетим каждого из дочерних узлов узла 1, узел 2 и узел 5. Вместо посещения непосещенных дочерних узлов узла 2, а затем узла 5. непосещенных детей, мы посещаем непосещенных детей Узла 2 и продолжаем исследовать этот путь, пока не дойдем до конца, прежде чем вернуться к Узлу 5.

Из Узла 2 мы посещаем Узел 3 и отмечаем Узел 2 как исследованный. Из узла 3 мы посещаем узел 4 и отмечаем узел 3 как исследованный, а из узла 4 мы посещаем узел 6 и отмечаем узел 4 как исследованный. Теперь мы видим, что нам некуда идти от узла 6, поэтому мы отмечаем его как исследованный и возвращаемся к узлу 5. Поскольку дочерние элементы узла 5 уже были посещены, мы отмечаем узел 5 как исследованный, и наш алгоритм завершается.

Различия

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

BFS: 1, 2, 5, 3, 4, 6
DFS: 1, 2, 3, 4, 6, 5

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