الگوریتم بروکا (Boruvka) یا همان الگوریتم سولین (Sollin)

الگوریتم Borůvka که با نام الگوریتم سولین هم شناخته می‌شود، یک الگوریتم حریصانه است که توسط Otakar Borůvka، ریاضی‌دان اهل کشور چک که‌ بیشتر به‌خاطر فعالیت‌هایش در نظریه گرافهمه چیز در مورد نظریه گراف (Graph Theory)در این مقاله یک مقدمه جامع در رابطه با نظریه گراف ارائه شده است و سعی شده نشان داده شود که دانستن برخی از مبانی نظریه گراف تا چه میزان می‌تواند مفید و موثر باشد. شناخته‌شده است، منتشرشده است. مهم‌ترین کاربرد این الگوریتمآموزش طراحی الگوریتم به زبان سادهدرس طراحی الگوریتم‌ یکی از مهم‌ترین و بنیادیترین دروس‌ رشته کامپیوتر است. هدف از این درس، معرفی روش‌های مختلف طراحی الگوریتم‌ها برای حل مسائل گوناگون است، در این صفحه به معرفی و آموزش طراحی الگوریتم پرداخته شده است. پیداکردن درخت پوشای کمینه در یک گراف است. در این مقاله ما به‌ بررسی این الگوریتم می‌پردازیم.

حتما بخوانید :

الگوریتم چیست

مراحل اجرای الگوریتم بروکا و مثال

الگوریتم بروکا یا سولین ساده‌ و‌ شهودی است. بروکا یک الگوریتم حریصانه است که‌ یک راه‌حل "بهینه سراسری" را با استفاده‌ از راه‌حل‌های کوچک‌تر و بهینه محلی برای مسائل فرعی کوچک‌تر می‌سازد. الگوریتم‌های حریصانه معمولاً سعی می‌کنند با برداشتن گام‌های کوچک و با پیداکردن بهینه‌های محلی، درنهایت به‌ بهینه سراسری برسند.

بیایید الگوریتم‌ را به‌ چند مرحله تقسیم کنیم:

یک گراف همبند، وزن‌دار و بدون جهت را به‌عنوان ورودی بگیرید.
تمام گره‌ها را به‌عنوان اجزای جداگانه در نظر بگیرید.
گراف خالی درخت پوشای کمینه (MST) را ایجاد کنید. (این گراف شامل جواب خواهد بود)
تا زمانی که بیش از یک جزء وجود دارد، عملیات زیر را انجام دهید.
- یال با وزن کمینه را که این جزء را به هر جزء دیگری متصل می‌کند، پیدا کنید.
- در صورتی‌که این یال از قبل در MST وجود ندارد، آن را به MST اضافه کنید.
اگر تنها یک جزء باقی‌مانده است، درخت پوشای کمینه را برگردانید.

حال بیایید در گراف زیر و با استفاده‌ از الگوریتم بروکا، درخت پوشای کمینه را پیدا کنیم:

در گراف بدون جهت بالا، 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

پس‌ از متصل‌کردن این اجزا گراف به‌ شکل زیر خواهد بود. (یال‌های سبزرنگ، یال‌هایی هستند که در درخت پوشای کمینه خواهند بود)

همان‌طور که می‌بینیم، اکنون اجزای زیر را داریم: {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

پس‌ از این مرحله، گراف ما به‌ شکل زیر خواهد بود:

پیاده سازی الگوریتم بروکا

Python

# Boruvka’s algorithm to find Minimum Spanning
# Tree of a given connected, undirected and weighted graph
 
from collections import defaultdict
 
#Class to represent a graph
class Graph:
 
    def __init__(self,vertices):
        self.V= vertices #No. of vertices
        self.graph = [] # default dictionary to store graph
         
  
    # function to add an edge to graph
    def addEdge(self,u,v,w):
        self.graph.append([u,v,w])
 
    # A utility function to find set of an element i
    # (uses path compression technique)
    def find(self, parent, i):
        if parent[i] == i:
            return i
        return self.find(parent, parent[i])
 
    # A function that does union of two sets of x and y
    # (uses union by rank)
    def union(self, parent, rank, x, y):
        xroot = self.find(parent, x)
        yroot = self.find(parent, y)
 
        # Attach smaller rank tree under root of high rank tree
        # (Union by Rank)
        if rank[xroot] < rank[yroot]:
            parent[xroot] = yroot
        elif rank[xroot] > rank[yroot]:
            parent[yroot] = xroot
        #If ranks are same, then make one as root and increment
        # its rank by one
        else :
            parent[yroot] = xroot
            rank[xroot] += 1
 
    # The main function to construct MST using Kruskal’s algorithm
    def boruvkaMST(self):
        parent = []; rank = [];
 
        # An array to store index of the cheapest edge of
        # subset. It store [u,v,w] for each component
        cheapest =[]
 
        # Initially there are V different trees.
        # Finally there will be one tree that will be MST
        numTrees = self.V
        MSTweight = 0
 
        # Create V subsets with single elements
        for node in range(self.V):
            parent.append(node)
            rank.append(0)
            cheapest =[-1] * self.V
     
        # Keep combining components (or sets) until all
        # components are not combined into single MST
 
        while numTrees > 1:
 
            # Traverse through all edges and update
               # cheapest of every component
            for I in range(len(self.graph)):
 
                # Find components (or sets) of two corners
                # of current edge
                u,v,w =  self.graph[i]
                set1 = self.find(parent, u)
                set2 = self.find(parent ,v)
 
                # If two corners of current edge belong to
                # same set, ignore current edge. Else check if
                # current edge is closer to previous
                # cheapest edges of set1 and 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]
 
            # Consider the above picked cheapest edges and add them
            # to MST
            for node in range(self.V):
 
                #Check if cheapest for current set exists
                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 array
            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()

# Boruvka’s algorithm to find Minimum Spanning
# Tree of a given connected, undirected and weighted graph
 
from collections import defaultdict
 
#Class to represent a graph
class Graph:
 
    def __init__(self,vertices):
        self.V= vertices #No. of vertices
        self.graph = [] # default dictionary to store graph
         
  
    # function to add an edge to graph
    def addEdge(self,u,v,w):
        self.graph.append([u,v,w])
 
    # A utility function to find set of an element i
    # (uses path compression technique)
    def find(self, parent, i):
        if parent[i] == i:
            return i
        return self.find(parent, parent[i])
 
    # A function that does union of two sets of x and y
    # (uses union by rank)
    def union(self, parent, rank, x, y):
        xroot = self.find(parent, x)
        yroot = self.find(parent, y)
 
        # Attach smaller rank tree under root of high rank tree
        # (Union by Rank)
        if rank[xroot] < rank[yroot]:
            parent[xroot] = yroot
        elif rank[xroot] > rank[yroot]:
            parent[yroot] = xroot
        #If ranks are same, then make one as root and increment
        # its rank by one
        else :
            parent[yroot] = xroot
            rank[xroot] += 1
 
    # The main function to construct MST using Kruskal’s algorithm
    def boruvkaMST(self):
        parent = []; rank = [];
 
        # An array to store index of the cheapest edge of
        # subset. It store [u,v,w] for each component
        cheapest =[]
 
        # Initially there are V different trees.
        # Finally there will be one tree that will be MST
        numTrees = self.V
        MSTweight = 0
 
        # Create V subsets with single elements
        for node in range(self.V):
            parent.append(node)
            rank.append(0)
            cheapest =[-1] * self.V
     
        # Keep combining components (or sets) until all
        # components are not combined into single MST
 
        while numTrees > 1:
 
            # Traverse through all edges and update
               # cheapest of every component
            for I in range(len(self.graph)):
 
                # Find components (or sets) of two corners
                # of current edge
                u,v,w =  self.graph[i]
                set1 = self.find(parent, u)
                set2 = self.find(parent ,v)
 
                # If two corners of current edge belong to
                # same set, ignore current edge. Else check if
                # current edge is closer to previous
                # cheapest edges of set1 and 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]
 
            # Consider the above picked cheapest edges and add them
            # to MST
            for node in range(self.V):
 
                #Check if cheapest for current set exists
                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 array
            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()

++C

// Boruvka’s algorithm to find Minimum Spanning
// Tree of a given connected, undirected and weighted graph
#include <bits/stdc++.h>
using namespace std;
 
// Class to represent a graph
class Graph {
    int V; // No. of vertices
    vectorvector >graph; // default dictionary to store graph
 
    // A utility function to find set of an element i
    // (uses path compression technique)
    int find(vector& parent, int i)
    {
        if (parent[i] == i) {
            return I;
        }
        return find(parent, parent[i]);
    }
 
    // A function that does union of two sets of x and y
    // (uses union by rank)
    void unionSet(vector<int>& parent, vector<int>& rank,
                  int x, int y)
    {
        int xroot = find(parent, x);
        int yroot = find(parent, y);
 
        // Attach smaller rank tree under root of high rank
        // tree (Union by Rank)
        if (rank[xroot]  rank[yroot]) {
            parent[xroot] = yroot;
        }
        else if (rank[xroot] > rank[yroot]) {
            parent[yroot] = xroot;
        }
        // If ranks are same, then make one as root and
        // increment its rank by one
        else {
            parent[yroot] = xroot;
            rank[xroot]++;
        }
    }
 
public:
    Graph(int vertices)
    {
        V = vertices;
        graph = vectorvector >();
    }
 
    // function to add an edge to graph
    void addEdge(int u, int v, int w)
    {
        graph.push_back({ u, v, w });
    }
 
    // The main function to construct MST using Kruskal’s
    // algorithm
    void boruvkaMST()
    {
        vector parent(V);
 
        // An array to store index of the cheapest edge of
        // subset. It store [u,v,w] for each component
        vector rank(V);
        vectorvector > cheapest(V,
                                      vector(3, -1));
 
        // Initially there are V different trees.
        // Finally there will be one tree that will be MST
        int numTrees = V;
        int MSTweight = 0;
 
        // Create V subsets with single elements
        for (int node = 0; node  V; node++) {
            parent[node] = node;
            rank[node] = 0;
        }
 
        // Keep combining components (or sets) until all
        // components are not combined into single MST
        while (numTrees > 1) {
 
            // Traverse through all edges and update
            // cheapest of every component
            for (int I = 0; I  w) {
                        cheapest[set1] = { u, v, w };
                    }
                    if (cheapest[set2][2] == -1
                        || cheapest[set2][2] > w) {
                        cheapest[set2] = { u, v, w };
                    }
                }
            }
 
            // Consider the above picked cheapest edges and
            // add them to MST
            for (int node = 0; node < V; node++) {
 
                // Check if cheapest for current set exists
                if (cheapest[node][2] != -1) {
                    int u = cheapest[node][0],
                        v = cheapest[node][1],
                        w = cheapest[node][2];
                    int set1 = find(parent, u),
                        set2 = find(parent, v);
                    if (set1 != set2) {
                        MSTweight += w;
                        unionSet(parent, rank, set1, set2);
                        printf(“Edge %d-%d with weight %d “
                               “included in MST\n”,
                               u, v, w);
                        numTrees--;
                    }
                }
            }
            for (int node = 0; node < V; node++) {
 
                // reset cheapest array
                cheapest[node][2] = -1;
            }
        }
        printf(“Weight of MST is %d\n”, MSTweight);
    }
};
int main()
{
    Graph g(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();
}

// Boruvka’s algorithm to find Minimum Spanning
// Tree of a given connected, undirected and weighted graph
#include <bits/stdc++.h>
using namespace std;
 
// Class to represent a graph
class Graph {
    int V; // No. of vertices
    vectorvector >graph; // default dictionary to store graph
 
    // A utility function to find set of an element i
    // (uses path compression technique)
    int find(vector& parent, int i)
    {
        if (parent[i] == i) {
            return I;
        }
        return find(parent, parent[i]);
    }
 
    // A function that does union of two sets of x and y
    // (uses union by rank)
    void unionSet(vector<int>& parent, vector<int>& rank,
                  int x, int y)
    {
        int xroot = find(parent, x);
        int yroot = find(parent, y);
 
        // Attach smaller rank tree under root of high rank
        // tree (Union by Rank)
        if (rank[xroot]  rank[yroot]) {
            parent[xroot] = yroot;
        }
        else if (rank[xroot] > rank[yroot]) {
            parent[yroot] = xroot;
        }
        // If ranks are same, then make one as root and
        // increment its rank by one
        else {
            parent[yroot] = xroot;
            rank[xroot]++;
        }
    }
 
public:
    Graph(int vertices)
    {
        V = vertices;
        graph = vectorvector >();
    }
 
    // function to add an edge to graph
    void addEdge(int u, int v, int w)
    {
        graph.push_back({ u, v, w });
    }
 
    // The main function to construct MST using Kruskal’s
    // algorithm
    void boruvkaMST()
    {
        vector parent(V);
 
        // An array to store index of the cheapest edge of
        // subset. It store [u,v,w] for each component
        vector rank(V);
        vectorvector > cheapest(V,
                                      vector(3, -1));
 
        // Initially there are V different trees.
        // Finally there will be one tree that will be MST
        int numTrees = V;
        int MSTweight = 0;
 
        // Create V subsets with single elements
        for (int node = 0; node  V; node++) {
            parent[node] = node;
            rank[node] = 0;
        }
 
        // Keep combining components (or sets) until all
        // components are not combined into single MST
        while (numTrees > 1) {
 
            // Traverse through all edges and update
            // cheapest of every component
            for (int I = 0; I  w) {
                        cheapest[set1] = { u, v, w };
                    }
                    if (cheapest[set2][2] == -1
                        || cheapest[set2][2] > w) {
                        cheapest[set2] = { u, v, w };
                    }
                }
            }
 
            // Consider the above picked cheapest edges and
            // add them to MST
            for (int node = 0; node < V; node++) {
 
                // Check if cheapest for current set exists
                if (cheapest[node][2] != -1) {
                    int u = cheapest[node][0],
                        v = cheapest[node][1],
                        w = cheapest[node][2];
                    int set1 = find(parent, u),
                        set2 = find(parent, v);
                    if (set1 != set2) {
                        MSTweight += w;
                        unionSet(parent, rank, set1, set2);
                        printf(“Edge %d-%d with weight %d “
                               “included in MST\n”,
                               u, v, w);
                        numTrees--;
                    }
                }
            }
            for (int node = 0; node < V; node++) {
 
                // reset cheapest array
                cheapest[node][2] = -1;
            }
        }
        printf(“Weight of MST is %d\n”, MSTweight);
    }
};
int main()
{
    Graph g(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();
}

مقایسه با الگوریتم های مشابه

مقایسه با الگوریتم کروسکال

در الگوریتم کروسکالالگوریتم کراسکال یا کروسکال⚡️مثال+پیاده سازی+پیچیدگی زمانیاین صفحه عالی به معرفی الگوریتم کراسکال یا کروسکال (Kruskal) پرداخته و مثالی از الگوریتم کروسکال و پیاده‌سازی و پچیدگی زمانی الگوریتم کروسکال را بررسی کرده ، اول‌ازهمه می‌خواهیم تمام یال‌ها را از سبک‌ترین به سنگین‌ترین آن‌ها مرتب کنیم. سپس در هر مرحله یال با کمترین یال‌ را حذف می‌کنیم و اگر یک دور در درخت‌ ما ایجاد نمی‌کند (که‌ در ابتدا از V| - 1| رأس جداگانه تشکیل شده است) آن‌ را به MST اضافه می‌کنیم. در غیر این‌ صورت فقط آن‌ را حذف می‌کنیم.

الگوریتم Boruvka به‌ دنبال نزدیک‌ترین همسایه هر جزء (در ابتدای رأس) است. همچنان کم‌وزن‌ترین یال‌ را از هر جزء انتخاب می‌کند و آن‌ را به MST ما اضافه می‌کند. وقتی فقط یک جزء متصل داشته باشیم، کار تمام است.

مقایسه با الگوریتم پریم

الگوریتم پریمالگوریتم پریم (Prim) چیست ⚡️مثال+پیاده سازی+پیچیدگی زمانیاین صفحه عالی به معرفی الگوریتم پریم (Prim) و مقایسه پریم و کروسکال پرداخته و مثالی از الگوریتم پریم و پیاده‌سازی و پچیدگی زمانی الگوریتم پریم را بررسی کرده ماهیت ترتیبی دارد. MST را در هر مرحله با گرفتن کم‌وزن‌ترین یال که دقیقاً یک انتهای آن در قسمت ازقبل ساخته‌شده MST دارد، یک رأس افزایش می‌دهد.

الگوریتم Borůvka ماهیت موازی دارد (و درواقع پایه‌ای برای الگوریتم‌های MST موازی کارآمد است). در هر مرحله، کم‌وزن‌ترین یال‌ را از هر رأس انتخاب می‌کند، همه آن‌ها را به‌یک‌باره به MST اضافه می‌کند و هر جزء متصل‌ را به‌ یک جزء متصل دیگر وصل می‌کند.

مزیت الگوریتم بروکا

مزیت قابل‌توجه الگوریتم Boruvka یا سولین این است که‌ به‌راحتی می‌توان آن‌ را به‌صورت موازی پیاده‌ کرد، زیرا انتخاب کم‌وزن‌ترین یال خروجی برای هر جزء کاملاً مستقل‌ از انتخاب‌های انجام‌شده توسط اجزای دیگر است.

کاربردهای الگوریتم بروکا

مهم‌ترین کاربرد این الگوریتم پیداکردن درخت پوشای کمینه یک گراف است.

جمع‌بندی

بسیاری‌ از الگوریتم‌های درخت پوشای کمینه محبوب دیگر مانند الگوریتم Prim یا Kruskal وجود دارد. بااین‌حال، الگوریتم Boruvka یا سولین، یک الگوریتم متفاوت نیست و تقریباً همان نتیجه‌ را می‌دهد. همه این الگوریتم‌ها درخت پوشای کمینه‌ را پیدا می‌کنند و پیچیدگی زمانیپیچیدگی زمانی الگوریتم چیست؟ معرفی نماد های مجانبیاین صفحه عالی به معرفی پیچیدگی زمانی الگوریتم پرداخته، همچنین انواع نماد های مجانبی و پیچیدگی زمانی های برخی از الگوریتم های مرتب سازی و جستجو را توضیح داده تقریباً یکسانی دارند. الگوریتم Boruvka مزایای بیشتری نسبت‌ به سایر الگوریتم‌ها دارد. برای یافتن درخت پوشای کمینه نیازی به‌ از‌ پیش مرتب‌کردن یال‌ها یا حفظ صف اولویت ندارد. در این مقاله، الگوریتم Boruvka، مثال آن و پیاده‌سازی آن‌ را مورد بررسی قرار دادیم.

آیا الگوریتم بروکا یک الگوریتم حریصانه است؟

الگوریتم Boruvka نیز مانند Prim و Kruskal یک الگوریتم حریصانه است.

کاربرد الگوریتم بروکا چیست؟

مهم‌ترین کاربرد این الگوریتم پیداکردن درخت پوشای کمینه یک گراف است.

مزیت الگوریتم بروکا نسبت به سایر الگوریتم های مشابه چیست؟

مزیت قابل‌توجه الگوریتم Boruvka این است که‌ به‌راحتی می‌توان آن‌ را به‌صورت موازی پیاده کرد، زیرا انتخاب کم‌وزن‌ترین یال خروجی برای هر جزء کاملاً مستقل‌ از انتخاب‌های انجام‌شده توسط اجزای دیگر است.