Алгоритм Борувки | Жадный Алго-9

// Алгоритм Борувки для нахождения минимального охвата
// Дерево данного связного, ненаправленного и
// взвешенный график
#include <stdio.h>

  
// структура для представления взвешенного ребра в графе

struct Edge

{

    int src, dest, weight;

};

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

struct Graph

{

    // V-> Количество вершин, E-> Количество ребер

    int V, E;

    // график представлен в виде массива ребер.

    // Так как график неориентирован, ребро

    // от src к dest также ребро от dest

    // в ср. И то и другое считается как 1 ребро.

    Edge* edge;

};

  
// Структура для представления подмножества для union-find

struct subset

{

    int parent;

    int rank;

};

  
// Прототипы функций для union-find (Эти функции определены
// после борувкаМСТ ())

int find(struct subset subsets[], int i);

void Union(struct subset subsets[], int x, int y);

  
// Основная функция для MST с использованием алгоритма Борувки

void boruvkaMST(struct Graph* graph)

{

    // Получить данные данного графика

    int V = graph->V, E = graph->E;

    Edge *edge = graph->edge;

    // Выделить память для создания V подмножеств.

    struct subset *subsets = new subset[V];

    // Массив для хранения индекса самого дешевого края

    // подмножество. Сохраненный индекс для индексации массива 'edge []'

    int *cheapest = new int[V];

    // Создать V подмножеств с отдельными элементами

    for (int v = 0; v < V; ++v)

    {

        subsets[v].parent = v;

        subsets[v].rank = 0;

        cheapest[v] = -1;

    }

    // Изначально существует V разных деревьев.

    // Наконец, будет одно дерево, которое будет MST

    int numTrees = V;

    int MSTweight = 0;

    // Продолжаем комбинировать компоненты (или наборы), пока все

    // Компоненты не объединяются в один MST.

    while (numTrees > 1)

    {

         // Каждый раз инициализируем самый дешевый массив

          for (int v = 0; v < V; ++v)

           {

               cheapest[v] = -1;

           }

        // Пройдите через все ребра и обновите

        // самый дешевый из каждого компонента

        for (int i=0; i<E; i++)

        {

            // Найти компоненты (или наборы) двух углов

            // текущего края

            int set1 = find(subsets, edge[i].src);

            int set2 = find(subsets, edge[i].dest);

            // Если два угла текущего ребра принадлежат

            // тот же набор, игнорировать текущее ребро

            if (set1 == set2)

                continue;

            // Иначе проверяем, находится ли текущий фронт ближе к предыдущему

            // самые дешевые ребра set1 и set2

            else

            {

               if (cheapest[set1] == -1 ||

                   edge[cheapest[set1]].weight > edge[i].weight)

                 cheapest[set1] = i;

               if (cheapest[set2] == -1 ||

                   edge[cheapest[set2]].weight > edge[i].weight)

                 cheapest[set2] = i;

            }

        }

        // Рассмотрим выбранные выше самые дешевые ребра и добавим их

        // в MST

        for (int i=0; i<V; i++)

        {

            // Проверяем, существует ли самый дешевый для текущего набора

            if (cheapest[i] != -1)

            {

                int set1 = find(subsets, edge[cheapest[i]].src);

                int set2 = find(subsets, edge[cheapest[i]].dest);

                if (set1 == set2)

                    continue;

                MSTweight += edge[cheapest[i]].weight;

                printf("Edge %d-%d included in MST\n",

                       edge[cheapest[i]].src, edge[cheapest[i]].dest);

                // Делаем объединение set1 и set2 и уменьшаем число

                // деревьев

                Union(subsets, set1, set2);

                numTrees--;

            }

        }

    }

    printf("Weight of MST is %d\n", MSTweight);

    return;

}

  
// Создаем граф с V вершинами и E ребрами

struct Graph* createGraph(int V, int E)

{

    Graph* graph = new Graph;

    graph->V = V;

    graph->E = E;

    graph->edge = new Edge[E];

    return graph;

}

  
// Полезная функция для поиска множества элементов i
// (использует технику сжатия пути)

int find(struct subset subsets[], int i)

{

    // найти root и сделать root родителем i

    // (сжатие пути)

    if (subsets[i].parent != i)

      subsets[i].parent =

             find(subsets, subsets[i].parent);

    return subsets[i].parent;

}

  
// Функция, которая объединяет два набора x и y
// (использует объединение по рангу)

void Union(struct subset subsets[], int x, int y)

{

    int xroot = find(subsets, x);

    int yroot = find(subsets, y);

    // Прикрепить дерево меньшего ранга под корень высокого

    // ранговое дерево (объединение по рангу)

    if (subsets[xroot].rank < subsets[yroot].rank)

        subsets[xroot].parent = yroot;

    else if (subsets[xroot].rank > subsets[yroot].rank)

        subsets[yroot].parent = xroot;

    // Если ранги одинаковы, то создайте их как root и

    // увеличиваем ранг на единицу

    else

    {

        subsets[yroot].parent = xroot;

        subsets[xroot].rank++;

    }

}

  
// Программа драйвера для проверки вышеуказанных функций

int main()

{

    / * Давайте создадим следующий взвешенный график

             10

        0 -------- 1

        | / |

       6 | 5 / | 15

        | / |

        2 -------- 3

            4 * /

    int V = 4;  // Количество вершин в графе

    int E = 5;  // Количество ребер в графе

    struct Graph* graph = createGraph(V, E);

    // добавляем ребро 0-1

    graph->edge[0].src = 0;

    graph->edge[0].dest = 1;

    graph->edge[0].weight = 10;

    // добавляем ребро 0-2

    graph->edge[1].src = 0;

    graph->edge[1].dest = 2;

    graph->edge[1].weight = 6;

    // добавляем ребро 0-3

    graph->edge[2].src = 0;

    graph->edge[2].dest = 3;

    graph->edge[2].weight = 5;

    // добавить ребро 1-3

    graph->edge[3].src = 1;

    graph->edge[3].dest = 3;

    graph->edge[3].weight = 15;

    // добавить ребро 2-3

    graph->edge[4].src = 2;

    graph->edge[4].dest = 3;

    graph->edge[4].weight = 4;

    boruvkaMST(graph);

    return 0;

}

  
// Спасибо Anukul Chand за изменение кода выше.

Алгоритм # Борувки для нахождения минимального охвата
# Дерево данного связного, ненаправленного и взвешенного графа

from collections import defaultdict

  
# Класс для представления графика

class Graph:

    def __init__(self,vertices):

        self.V= vertices #No. вершин

        self.graph = [] # словарь по умолчанию для хранения графика

    # функция для добавления ребра на график

    def addEdge(self,u,v,w):

        self.graph.append([u,v,w])

    # Полезная функция для поиска множества элементов i

    # (использует метод сжатия пути)

    def find(self, parent, i):

        if parent[i] == i:

            return i

        return self.find(parent, parent[i])

    # Функция, которая объединяет два набора x и y

    # (использует объединение по рангу)

    def union(self, parent, rank, x, y):

        xroot = self.find(parent, x)

        yroot = self.find(parent, y)

        # Присоединить дерево меньшего ранга под корнем дерева высокого ранга

        # (Союз по рангу)

        if rank[xroot] < rank[yroot]:

            parent[xroot] = yroot

        elif rank[xroot] > rank[yroot]:

            parent[yroot] = xroot

        # Если ранги одинаковы, то сделать их корнем и увеличить

        # его ранг на единицу

        else :

            parent[yroot] = xroot

            rank[xroot] += 1

    # Основная функция для построения MST с использованием алгоритма Крускала

    def boruvkaMST(self):

        parent = []; rank = []; 

        # Массив для хранения индекса самого дешевого края

        # подмножество. Он хранит [u, v, w] для каждого компонента

        cheapest =[]

        # Изначально существует V разных деревьев.

        # Наконец, будет одно дерево, которое будет MST

        numTrees = self.V

        MSTweight = 0

        # Создание V подмножеств с отдельными элементами

        for node in range(self.V):

            parent.append(node)

            rank.append(0)

            cheapest =[-1] * self.V

        # Продолжайте комбинировать компоненты (или наборы), пока все

        # Компоненты не объединяются в один MST

        while numTrees > 1:

            # Пройдите через все края и обновите

               # самый дешевый из каждого компонента

            for i in range(len(self.graph)):

                # Найти компоненты (или наборы) двух углов

                # текущего фронта

                u,v,w =  self.graph[i]

                set1 = self.find(parent, u)

                set2 = self.find(parent ,v)

                # Если два угла текущего ребра принадлежат

                # тот же набор, игнорировать текущий фронт. Еще проверьте, если

                # текущее ребро ближе к предыдущему

                # самые дешевые ребра set1 и set2

                if set1 != set2:     

                    if cheapest[set1] == -1 or cheapest[set1][2] > w :

                        cheapest[set1] = [u,v,w] 

                    if cheapest[set2] == -1 or cheapest[set2][2] > w :

                        cheapest[set2] = [u,v,w]

            # Рассмотрите вышеупомянутые выбранные самые дешевые края и добавьте их

            # до MST

            for node in range(self.V):

                # Проверьте, существует ли самый дешевый для текущего набора

                if cheapest[node] != -1:

                    u,v,w = cheapest[node]

                    set1 = self.find(parent, u)

                    set2 = self.find(parent ,v)

                    if set1 != set2 :

                        MSTweight += w

                        self.union(parent, rank, set1, set2)

                        print ("Edge %d-%d with weight %d included in MST" % (u,v,w))

                        numTrees = numTrees - 1

            #reset самый дешевый массив

            cheapest =[-1] * self.V

        print ("Weight of MST is %d" % MSTweight)

g = Graph(4)

g.addEdge(0, 1, 10)

g.addEdge(0, 2, 6)

g.addEdge(0, 3, 5)

g.addEdge(1, 3, 15)

g.addEdge(2, 3, 4)

  
g.boruvkaMST()

  
# Этот код предоставлен Ниламом Ядавом