Рубрики

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

Мы обсудили следующие темы о минимальном остовном дереве.

Приложения задачи минимального остовного дерева
Алгоритм минимального связующего дерева Крускала
Минимальный алгоритм связующего дерева Прима

В этом посте обсуждается алгоритм Борувки. Как и у Прима и Крускала, алгоритм Борувки также является алгоритмом Жадности. Ниже приведен полный алгоритм.

1) Input is a connected, weighted and directed graph.
2) Initialize all vertices as individual components (or sets).
3) Initialize MST as empty.
4) While there are more than one components, do following
   for each component.
      a)  Find the closest weight edge that connects this 
          component to any other component.
      b)  Add this closest edge to MST if not already added.  
5) Return MST.

Ниже приведена идея вышеупомянутого алгоритма (идея такая же, как и у алгоритма MST Прима ).

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

Давайте разберемся с алгоритмом на примере ниже.

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

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

Component                Cheapest Edge that connects 
                         it to some other component
  {0}                           0-1
  {1}                           0-1
  {2}                           2-8
  {3}                           2-3
  {4}                           3-4
  {5}                           5-6
  {6}                           6-7
  {7}                           6-7
  {8}                           2-8 

Самые дешевые края выделены зеленым цветом. Теперь MST становится {0-1, 2-8, 2-3, 3-4, 5-6, 6-7}.

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

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

Component                Cheapest Edge that connects 
                         it to some other component
  {0,1}                        1-2 (or 0-7)
  {2,3,4,8}                    2-5
  {5,6,7}                      2-5

Самые дешевые края выделены зеленым цветом. Теперь MST становится {0-1, 2-8, 2-3, 3-4, 5-6, 6-7, 1-2, 2-5}

На этом этапе есть только один компонент {0, 1, 2, 3, 4, 5, 6, 7, 8}, который имеет все ребра. Поскольку остался только один компонент, мы останавливаемся и возвращаем MST.

Реализация:
Ниже приведена реализация вышеуказанного алгоритма. Входной граф представлен в виде набора ребер, а структура данных union-find используется для отслеживания компонентов.

C / C ++

// Алгоритм Борувки для нахождения минимального охвата
// Дерево данного связного, ненаправленного и
// взвешенный график
#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()

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


Выход:

Edge 0-3 included in MST
Edge 0-1 included in MST
Edge 2-3 included in MST
Weight of MST is 19

Интересные факты об алгоритме Борувки:
1) Сложность времени алгоритма Борувки равна O (E log V), что совпадает с алгоритмами Крускала и Прима.

2) Алгоритм Борувки используется в качестве шага в более быстром рандомизированном алгоритме, который работает за линейное время O (E) .

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

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

Ссылки:
http://en.wikipedia.org/wiki/Bor%C5%AFvka%27s_algorithm

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

Рекомендуемые посты:

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

0.00 (0%) 0 votes