В прошлый раз, когда мы встретились, мы обсуждали концепцию графов в CS. В очень общем виде мы поговорили о том, что такое График, о различиях между Направленными и Ненаправленными графиками, а также о некоторых наиболее распространенных категориях графиков, с которыми вы можете столкнуться в дикой природе. Если вы не читали эту статью или вам нужно освежиться, прежде чем двигаться дальше, вы можете прочитать ее здесь.
Сегодня я собираюсь взглянуть на реализацию очень простого неориентированного графа в Ruby. Сохраним обходы и другие алгоритмы для следующего раза. На данный момент мы сосредоточимся исключительно на реализации класса Graph.
Это можно сделать несколькими способами, в том числе с помощью списка смежности или матрицы смежности. Я решил использовать реализацию списка смежности. В основном потому, что для меня это имеет наибольший смысл и, вероятно, это самый простой способ реализовать структуру данных Graph.
Итак, что такое список смежности? Это просто список узлов, которые примыкают к данному узлу. Возьмите простой неориентированный циклический график, показанный ниже.
В этом графе каждый узел будет иметь связанный с ним список смежности. В каждом из этих списков смежности будет по два узла.
- Узел a → смежный с [b, c]
- Узел b → смежный с [a, c]
- Узел c → смежный с [a, b]
Вот и все, нам просто нужно отслеживать список узлов, подключенных к данному узлу. Давайте реализуем класс Node, который сделает это.
Вот и все, наш класс Node, использующий список смежности. Это очень похоже на узлы, которые мы использовали в прошлом для связанных списков и деревьев. Основные отличия заключаются в том, что он создается с пустым списком, представляющим соседние узлы, и имеет функцию add_edge, которая позволяет нам соединять два узла.
Следующим шагом является реализация класса Graph, который использует наш новый класс Node. Есть несколько способов сделать это. Мы могли бы отслеживать узлы в графике, используя список или, еще лучше, набор, чтобы гарантировать уникальные узлы. Однако я решил использовать хеш. В основном потому, что это позволяет нам вести список узлов, у которых будут ключи в зависимости от их значения. Это позволяет нам быстро найти узел на графике. Посмотрите это ниже.
Несколько замечаний. Сначала метод add_node использует значение узла для создания ключа в хэше @nodes и устанавливает его равным переданному ему node. Этот метод, очевидно, может выиграть от некоторых проверок, чтобы увидеть, существует ли уже значение узла в хэше @nodes. Я оставил это для простоты и демонстрационных целей.
Еще одно замечание - это метод add_edge. Поскольку мы реализуем неориентированный граф, нам нужно добавить два ребра. Один от node1 до node2 и наоборот.
Вот и все, что нужно сделать. В следующий раз наступит самое интересное. Как эффективно перемещаться по графу? Подобно обходу дерева, мы можем делать это в первую очередь в глубину или в ширину. Добавьте сюда утяжеленные грани, и вы столкнетесь с еще более сложной проблемой. Ознакомьтесь с некоторыми из чтения ниже, пока мы в следующий раз не реализуем некоторые из этих обходов.
