Вступление

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

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

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

• Графики и минимальные остовные деревья
• Алгоритм Боровки.
• Выполнение

Графики и минимальные остовные деревья

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

Дерево - это пример графа:

{.ezlazyload}

На изображении выше первый граф имеет 4 узла и 4 ребра , а второй граф ( двоичное дерево ) имеет 7 узлов и 6 ребер .

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

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

{.ezlazyload}

Типы графиков

В зависимости от типов ребер у графа есть две различные категории графов:

• Ненаправленные графы
• Направленные графы

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

Формально мы можем определить неориентированный граф как G = (V, E) где V - это набор всех узлов графа, а E - это набор, содержащий неупорядоченные пары элементов из E , которые представляют ребра.

Неупорядоченные пары здесь означают, что отношения между двумя узлами всегда двусторонние, поэтому, если мы знаем, что есть ребро, идущее от A к B , мы точно знаем, что есть ребро, которое идет от B к A

Ориентированный граф - это граф, в котором ребра ориентированы.

Формально мы можем определить ориентированный граф как G = (V, E) где V - множество всех узлов графа, а E - множество, которое содержит упорядоченные пары элементов из E.

Упорядоченные пары подразумевают, что отношения между двумя узлами могут быть как односторонними, так и двусторонними. Это означает, что если есть ребро, идущее от A к B , мы не можем знать, есть ли ребро, идущее от B к A

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

{.ezlazyload}

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

• Взвешенный
• Невзвешенный

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

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

Невзвешенный граф не имеет весов на ребрах.

Примечание. В этой статье мы сосредоточимся на неориентированных взвешенных графах .

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

{.ezlazyload}

Деревья и минимальные остовные деревья

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

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

• Подграф графа A - это граф, состоящий из подмножества узлов и ребер A

• Остовное дерево графа A - это подграф графа A который является деревом, чей набор узлов такой же, как у графа A

• Минимальное остовное дерево - это остовное дерево, такое, что сумма всех весов ребер является минимально возможной. Поскольку это дерево (а сумма весов ребер должна быть минимальной), циклов быть не должно.

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

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

Алгоритм Боровки.

Идея этого алгоритма довольно проста и интуитивно понятна. Ранее мы упоминали, что это был жадный алгоритм.

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

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

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

Теперь мы разберем алгоритм на пару шагов:

1. Мы инициализируем все узлы как отдельные компоненты.
2. Мы инициализируем минимальное остовное дерево S как пустой набор, который будет содержать решение.
3. Если компонентов более одного:
   • Найдите ребро с минимальным весом, которое соединяет этот компонент с любым другим компонентом.
   • Если этого ребра нет в минимальном остовном дереве S , мы добавляем его.
4. Если остался только один компонент, мы достигли конца дерева.

Этот алгоритм принимает на вход связанный, взвешенный и неориентированный граф , а его выходом является соответствующее минимальное остовное дерево графа.

Давайте посмотрим на следующий график и найдем его минимальное остовное дерево с помощью алгоритма Боравки:

{.ezlazyload}

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

Составная часть Ребро наименьшего веса, которое соединяет его с другим компонентом Вес края {0} 0 - 1 4 {1} 0 - 1 4 {2} 2–4 2 {3} 3–5 5 {4} 4–7 1 {5} 3–5 10 {6} 6–7 1 {7} 4–7 1 {8} 7–8 3

Теперь наш график будет в этом состоянии:

{.ezlazyload}

Зеленые ребра на этом графике представляют ребра, которые связывают его ближайшие компоненты. Как мы видим, теперь у нас есть три компонента: {0, 1} , {2, 4, 6, 7, 8} и {3, 5} . Мы повторяем алгоритм и пытаемся найти ребра с минимальным весом, которые могут связать вместе эти компоненты:

Составная часть Ребро наименьшего веса, которое соединяет его с другим компонентом Вес края {0, 1} 0–6 7 {2, 4, 6, 7, 8} 2–3 6 {3, 5} 2–3 6

Теперь наш график будет в этом состоянии:

{.ezlazyload}

Как мы видим, у нас остался только один компонент в этом графе, который представляет наше минимальное остовное дерево! Вес этого дерева равен 29, что мы получили после суммирования всех ребер:

{.ezlazyload}

Теперь осталось только реализовать этот алгоритм на Python.

Выполнение

Мы собираемся реализовать Graph , который будет основной структурой данных, с которой мы будем работать. Начнем с конструктора:

 class Graph: 
 def __init__(self, num_of_nodes): 
 self.m_v = num_of_nodes 
 self.m_edges = [] 
 self.m_component = {} 

В этом конструкторе мы предоставили количество узлов в графе в качестве аргумента и инициализировали три поля:

• m_v - количество узлов в графе.
• m_edges - список ребер.
• m_component - словарь, в котором хранится индекс компонента, которому принадлежит узел.

Теперь давайте создадим вспомогательную функцию, которую мы можем использовать для добавления ребра к узлам графа:

 def add_edge(self, u, v, weight): 
 self.m_edges.append([u, v, weight]) 

Эта функция добавит к нашему графику [first, second, edge weight]

Поскольку мы хотим в конечном итоге создать метод, объединяющий два компонента, нам сначала понадобится метод, который распространяет новый компонент по данному компоненту. А во-вторых, нам понадобится метод, который находит индекс компонента данного узла:

 def find_component(self, u): 
 if self.m_component[u] == u: 
 return u 
 return self.find_component(self.m_component[u]) 
 
 def set_component(self, u): 
 if self.m_component[u] == u: 
 return 
 else: 
 for k in self.m_component.keys(): 
 self.m_component[k] = self.find_component(k) 

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

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

Например, на нашем графике в приведенном выше примере на первой итерации словарь будет выглядеть так:

индекс значение 0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8

У нас есть 9 компонентов, и каждый член сам по себе является компонентом. Во второй итерации это будет выглядеть так:

индекс значение 0 0 1 0 2 2 3 3 4 2 5 3 6 7 7 4 8 7

Теперь, возвращаясь к корням, мы увидим, что нашими новыми компонентами будут: {0, 1} , {2, 4, 7, 6, 8} и {3, 5} .

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

 def union(self, component_size, u, v): 
 if component_size[u] <= component_size[v]: 
 self.m_component[u] = v 
 component_size[v] += component_size[u] 
 self.set_component(u) 
 
 elif component_size[u] >= component_size[v]: 
 self.m_component[v] = self.find_component(u) 
 component_size[u] += component_size[v] 
 self.set_component(v) 
 
 print(self.m_component) 

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

Наконец, если компоненты имеют одинаковый размер, мы просто объединяем их вместе, как мы хотим - в этом конкретном примере мы сделали это, добавив второй компонент к первому.

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

 def boruvka(self): 
 component_size = [] 
 mst_weight = 0 
 
 minimum_weight_edge = [-1] * self.m_v 
 
 for node in range(self.m_v): 
 self.m_component.update({node: node}) 
 component_size.append(1) 
 
 num_of_components = self.m_v 
 
 print("---------Forming MST------------") 
 while num_of_components > 1: 
 for i in range(len(self.m_edges)): 
 
 u = self.m_edges[i][0] 
 v = self.m_edges[i][1] 
 w = self.m_edges[i][2] 
 
 u_component = self.m_component[u] 
 v_component = self.m_component[v] 
 
 if u_component != v_component: 
 if minimum_weight_edge[u_component] == -1 or \ 
 minimum_weight_edge[u_component][2] > w: 
 minimum_weight_edge[u_component] = [u, v, w] 
 if minimum_weight_edge[v_component] == -1 or \ 
 minimum_weight_edge[v_component][2] > w: 
 minimum_weight_edge[v_component] = [u, v, w] 
 
 for node in range(self.m_v): 
 if minimum_weight_edge[node] != -1: 
 u = minimum_weight_edge[node][0] 
 v = minimum_weight_edge[node][1] 
 w = minimum_weight_edge[node][2] 
 
 u_component = self.m_component[u] 
 v_component = self.m_component[v] 
 
 if u_component != v_component: 
 mst_weight += w 
 self.union(component_size, u_component, v_component) 
 print("Added edge [" + str(u) + " - " 
 + str(v) + "]\n" 
 + "Added weight: " + str(w) + "\n") 
 num_of_components -= 1 
 
 minimum_weight_edge = [-1] * self.m_v 
 print("----------------------------------") 
 print("The total weight of the minimal spanning tree is: " + str(mst_weight)) 

Первое, что мы сделали в этом алгоритме, это инициализировали дополнительные списки, которые нам понадобятся в алгоритме:

• Список компонентов (инициализирован для всех узлов).
• Список, в котором хранится их размер (инициализированный равным 1 ), а также список ребер с минимальным весом ( -1 , так как мы еще не знаем, каковы ребра с минимальным весом).

Затем мы перебираем все ребра в графе и находим корень компонентов по обе стороны от этих ребер.

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

• Если текущий край минимального веса компонента u не существует (равен -1 ) или если он больше, чем край, который мы наблюдаем прямо сейчас, мы присвоим ему значение края, который мы наблюдаем.
• Если текущий край минимального веса компонента v не существует (равен -1 ) или если он больше, чем край, который мы наблюдаем прямо сейчас, мы присвоим ему значение края, который мы наблюдаем.

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

Наконец, мы сбрасываем список ребер с минимальным весом обратно на -1 , чтобы мы могли сделать все это снова. Мы продолжаем повторять до тех пор, пока в списке компонентов есть более одного компонента.

Давайте поместим график, который мы использовали в примере выше, в качестве входных данных для нашего реализованного алгоритма:

 g = Graph(9) 
 g.add_edge(0, 1, 4) 
 g.add_edge(0, 6, 7) 
 g.add_edge(1, 6, 11) 
 g.add_edge(1, 7, 20) 
 g.add_edge(1, 2, 9) 
 g.add_edge(2, 3, 6) 
 g.add_edge(2, 4, 2) 
 g.add_edge(3, 4, 10) 
 g.add_edge(3, 5, 5) 
 g.add_edge(4, 5, 15) 
 g.add_edge(4, 7, 1) 
 g.add_edge(4, 8, 5) 
 g.add_edge(5, 8, 12) 

Забросив его в реализацию алгоритма, вы получите:

 ---------Forming MST------------ 
 {0: 1, 1: 1, 2: 2, 3: 3, 4: 4, 5: 5, 6: 6, 7: 7, 8: 8} 
 Added edge [0 - 1] 
 Added weight: 4 
 
 {0: 1, 1: 1, 2: 4, 3: 3, 4: 4, 5: 5, 6: 6, 7: 7, 8: 8} 
 Added edge [2 - 4] 
 Added weight: 2 
 
 {0: 1, 1: 1, 2: 4, 3: 5, 4: 4, 5: 5, 6: 6, 7: 7, 8: 8} 
 Added edge [3 - 5] 
 Added weight: 5 
 
 {0: 1, 1: 1, 2: 4, 3: 5, 4: 4, 5: 5, 6: 6, 7: 4, 8: 8} 
 Added edge [4 - 7] 
 Added weight: 1 
 
 {0: 1, 1: 1, 2: 4, 3: 5, 4: 4, 5: 5, 6: 4, 7: 4, 8: 8} 
 Added edge [6 - 7] 
 Added weight: 1 
 
 {0: 1, 1: 1, 2: 4, 3: 5, 4: 4, 5: 5, 6: 4, 7: 4, 8: 4} 
 Added edge [7 - 8] 
 Added weight: 3 
 
 {0: 4, 1: 4, 2: 4, 3: 5, 4: 4, 5: 5, 6: 4, 7: 4, 8: 4} 
 Added edge [0 - 6] 
 Added weight: 7 
 
 {0: 4, 1: 4, 2: 4, 3: 4, 4: 4, 5: 4, 6: 4, 7: 4, 8: 4} 
 Added edge [2 - 3] 
 Added weight: 6 
 
 ---------------------------------- 
 The total weight of the minimal spanning tree is: 29 

Временная сложность этого алгоритма составляет O(ElogV) , где E представляет количество ребер, а V представляет количество узлов.

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

Заключение

Хотя алгоритм Боравки не так хорошо известен, как некоторые другие алгоритмы минимального остовного дерева, такие как алгоритмы минимального остовного дерева Прима или Крускала, он дает нам практически тот же результат - все они находят минимальное остовное дерево, а временная сложность приблизительно равна тоже самое.

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