Освоение структур данных в Ruby — Графики

Граф — это структура данных, которая позволяет нам представлять данные в терминах объектов и отношений. Объекты на графике называются вершины (или узлы), а их соединения с другими узлами называются края.

   A <-- (this is vertex/node.)
  / \ 
 B - C 
  \ / <- (this is an edge.) 
   D

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

Ориентированные графы могут быть циклический когда узел указывает на узел, который на него ссылается, или ациклический когда нет обратных указателей. Например, генераторы кода компилятора могут преобразовывать AST (абстрактные синтаксические деревья) в ДЕНЬ s (направленные ациклические графы) перед отправкой кода для целевой платформы.

     A
    / \
   /   \ 
  v     v 
 B -----> C

* Направленный ациклический граф.

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

Интерфейс для графиков

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

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

Методы

Графический интерфейс.

Детали реализации

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

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

Вот как выглядит ASCII-представление этой структуры данных:

[vertex | {edges} | next] -> [vertex | {edges} | next] -> X (nil)

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

Для представления ребер на графе мы используем установить структуру данных которые мы построили ранее на этой серии.

Инициализировать

Этот метод является конструктором графа, и единственное, что он делает, — это инициализирует список вершин.

Сложность этого метода в том, О(1).

def initialize
  @vertices = LinkedList.new
end

Найти вершину

Этот метод находит вершину на основе ее ключа.

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

def find_vertex key
  @vertices.find_first { |v| v.data.key == key }
end

Вставить вершину

Этот метод добавляет вершину в граф.

Поскольку этот метод должен гарантировать, что граф не содержит дубликатов, его сложность На), куда н — количество вершин в графе.

def insert_vertex key
  return if find_vertex key
  vertex = Vertex.new key 
  @vertices.insert vertex
end

Вставить край

Этот метод соединяет два узла, добавляя к графу ребро.

Сложность этого метода в том, На), куда н — количество вершин в графе.

def insert_edge key1, key2
  # The graph must contains vertices.
  v1 = find_vertex key1
  return unless v1
  v2 = find_vertex key2
  return unless v2
  v1.data.edges.insert v2.data.key
end

Удалить вершину

Этот метод удаляет вершину из графа.

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

Первое, что нам нужно сделать, это найти вершину, соответствующую ключу, который мы хотим удалить. На этот раз мы не можем использовать стандарт найти_вершину метод потому что что нам нужен узел, который содержит вершину в списке вершин, а также тот, который предшествует ей. Имея эти узлы, мы можем удалить целевую вершину за постоянное время.

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

Если мы пройдём предыдущую проверку, узел можно будет безопасно удалить; Для этого мы используем узел, который предшествует целевому узлу (захвачено во время поиска) и вызвал метод удалить_следующий на модифицированной версии односвязного списка, который мы используем для хранения вершин.

Сложность этого метода в том, О (н + е), куда н — количество вершин в графе и е это количество ребер.

def remove_vertex key
  found  = false
  target = nil
  prev   = nil

  @vertices.each do |v|
    return if v.data.edges.contains? key
    if v.data.key == key
      found = true
      target = v.data
    end
    prev = v unless found
  end

  return unless found
  return unless target.edges.length == 0
  @vertices.remove_next prev
end

Удалить край

Этот метод удаляет из графа ребро, соединяющее указанные узлы.

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

Сложность этого метода в том, На), куда н — количество вершин в графе.

def remove_edge key1, key2
  vertex = find_vertex(key1)&.data
  return unless vertex  
  vertex.edges.remove key2
end

Соседний?

Этот метод сообщает, являются ли две вершины (узлы) смежными или нет.

Как и в случае с remove_edge, мы сначала ищем вершину, которая соответствует первому ключу, и если мы ее нашли, то проверяем, содержит ли ее коллекция ребер второй ключ, если да, то узлы являются смежными.

Сложность этого метода в том, На), куда н — количество вершин в графе.

def adjacent? key1, key2
  vertex = find_vertex(key1)&.data
  return true if vertex&.edges.contains? key2
  return false
end

Распечатать

Этот метод печатает содержимое текущего графика.

Сложность этого метода в том, О (н + е), куда н — количество вершин в графе, а e — количество ребер..

def print
  @vertices.each do |v|
    puts "#{v.data} (vertex)"
    v.data.edges.each do |e|
      puts " #{e.data} (edge)"
    end
  end
end

Когда использовать графики

Графики можно использовать для решения практически любых задач:

• Чтобы получить кратчайший путь между двумя точками на карте.
• Для подсчета сетевых переходов.
• Сделать топологическую сортировку
• Для представления зависимостей от программных систем.
• Чтобы организовать генерацию кода на компиляторах.
• Для представления коммитов в системах управления исходным контентом, таких как git.
• И многое другое, конечно.

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

Конечно, о графах можно рассказать намного больше, но это краткое введение. Я надеюсь, что вам понравилось!

Следующий пост, [Persistent lists]. Следите за обновлениями!

Как обычно, вы можете получить исходный код отсюда.

Спасибо за чтение!

PS: если вы являетесь участником программы Kindle Unlimited, вы можете прочитать немного отполированную версию этой серии бесплатно на вашем устройстве Kindle.

Структуры данных с нуля — Ruby Edition.