Освойте алгоритм Борувки с помощью Python: руководство для начинающих

Алгоритм Борувки Python

Алгоритм Борувки Python

Алгоритм Борувки — известный алгоритм, используемый для поиска минимального остовного дерева (MST) графа. В этой статье мы рассмотрим тонкости алгоритма Борувки и его реализацию на Python.

Введение в минимальные остовные деревья (MST)

Алгоритм Борувки Python

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

Что такое алгоритм Борувки?

Алгоритм Борувки, также известный как алгоритм Соллинза, представляет собой жадный алгоритм, используемый для поиска минимального остовного дерева графа. Впервые он был представлен Отакаром Борувкой в ​​1926 году, а затем оптимизирован Ю. Н. Соллиным в 1963 году.

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

Реализация алгоритма Борувки на Python

https://youtube.com/watch?v=4jBJhCaNrWU

Теперь, когда у нас есть понимание алгоритма Борувки, давайте посмотрим, как мы можем реализовать его на Python.

  Importing necessary libraries
from collections import defaultdict Class representing a graph class Graph: def __init__(self, vertices): self.V = vertices self.graph = [] Function to add an edge to the graph def add_edge(self, src, dest, weight): self.graph.append([src, dest, weight]) Function to find the parent of a node def find_parent(self, parent, i): if parent[i] == i: return i return self.find_parent(parent, parent[i]) Function that performs union of two sets def union(self, parent, rank, x, y): x_root = self.find_parent(parent, x) y_root = self.find_parent(parent, y) if rank[x_root] < rank[y_root]: parent[x_root] = y_root elif rank[x_root] > rank[y_root]: parent[y_root] = x_root else: parent[y_root] = x_root rank[x_root] += 1 Function to find the MST def boruvka(self): parent = [] rank = [] cheapest = [] num_trees = self.V minimum_cost = 0 for node in range(self.V): parent.append(node) rank.append(0) cheapest = [-1] * self.V while num_trees > 1: for i in range(len(self.graph)): src, dest, weight = self.graph[i] set1 = self.find_parent(parent, src) set2 = self.find_parent(parent, dest) if set1 != set2: if cheapest[set1] == -1 or weight < self.graph[cheapest[set1]][2]: cheapest[set1] = i if cheapest[set2] == -1 or weight < self.graph[cheapest[set2]][2]: cheapest[set2] = i for node in range(self.V): if cheapest[node] != -1: src, dest, weight = self.graph[cheapest[node]] set1 = self.find_parent(parent, src) set2 = self.find_parent(parent, dest) if set1 != set2: minimum_cost += weight self.union(parent, rank, set1, set2) print(fEdge: {src} -- {dest}\tWeight: {weight}) num_trees -= 1 cheapest = [-1] * self.V return minimum_cost Driver code to test the implementation if __name__ == __main__: g = Graph
 g.add_edge(0, 1, 10) g.add_edge(0, 2, 6) g.add_edge(0, 3, 5) g.add_edge(1, 3, 15) g.add_edge(2, 3, 4) print(Minimum Spanning Tree:) min_cost = g.boruvka() print(fMinimum Cost: {min_cost})

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

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

Заключение

Алгоритм Борувки Python

Алгоритм Борувки — эффективный и широко используемый алгоритм поиска минимального остовного дерева графа. Его жадный подход позволяет выполнять быстрые вычисления и обеспечивает наименьшее возможное дерево, охватывающее все узлы. Реализуя алгоритм Борувки на Python, мы можем легко найти минимальное связующее дерево любого связного графа.

Часто задаваемые вопросы

Алгоритм Борувки Python

  1. Что такое минимальное связующее дерево (MST)?

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

  2. Что такое алгоритм Борувки?

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

  3. Почему алгоритм Борувки эффективен?

    Алгоритм Борувки имеет временную сложность O(E log V), что делает его эффективным для поиска минимального остовного дерева больших графов.

  4. Может ли алгоритм Борувки обрабатывать несвязные графы?

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

  5. Оптимален ли алгоритм Борувки?

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

➤