АЛГОРИТМ БОРУВКИ PYTHON

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

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

def boruvka(graph):    parent = {}    rank = {}    for i in range(len(graph)):        parent[i] = i        rank[i] = 0    num_trees = len(graph)    while num_trees > 1:        cheapest = [None] * len(graph)        for i in range(len(graph)):            for j in graph[i]:                root_i = find(parent, i)                root_j = find(parent, j)                if root_i != root_j:                    if cheapest[root_i] is None or graph[i][j] < graph[cheapest[root_i]][root_i]:                        cheapest[root_i] = j                    if cheapest[root_j] is None or graph[i][j] < graph[cheapest[root_j]][root_j]:                        cheapest[root_j] = j        for i in range(len(graph)):            if cheapest[i] is not None:                root_i = find(parent, i)                root_j = find(parent, cheapest[i])                if root_i != root_j:                    if rank[root_i] > rank[root_j]:                        parent[root_j] = root_i                    else:                        parent[root_i] = root_j                        if rank[root_i] == rank[root_j]:                            rank[root_j] += 1                    num_trees -= 1    return parent  def find(parent, i):    if parent[i] == i:        return i    return find(parent, parent[i])

Здесь функция "boruvka()" принимает на вход взвешенный граф в виде словаря, а возвращает массив родителей для каждой вершины в минимальном остовном дереве. Функция "find()" используется для поиска корня дерева, к которому принадлежит вершина.

Aulas Python - 062 - POO IV: Herança, Super e Polimorfismo

#2. Алгоритм Бойера-Мура-Хорспула - Алгоритмы на Python

#3. Алгоритм Дейкстры (Dijkstra’s algorithm) - Алгоритмы на Python

Boruvkas Algorithm in Python OOP

Алгоритм Борувки: поиск остовного дерева.

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

BLGPG-C80C506E7942-24-09-19-20

Новые материалы: