الگوریتم بروکا (Boruvka’s Algorithm) — راهنمای کاربردی

۵۵۲ بازدید
آخرین به‌روزرسانی: ۱۲ خرداد ۱۴۰۳
زمان مطالعه: ۷ دقیقه
الگوریتم بروکا (Boruvka’s Algorithm) — راهنمای کاربردی

در این مطلب، «الگوریتم بروکا» (Boruvka’s Algorithm) مورد بررسی قرار گرفته و پیاده‌سازی آن در زبان‌های برنامه‌نویسی C++/C و پایتون انجام شده است. الگوریتم بروکا نیز مانند «الگوریتم پریم» (Prim's Algorithm) و «الگوریتم کراسکال» (Kruskal Algorithm)، یک «الگوریتم حریصانه» (Greedy Algorithm) است.

997696

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

در زیر، الگوریتم بروکا به طور کامل ارائه شده است.

  1. ورودی، یک گراف متصل، وزن‌دار و غیر جهت‌دار است.
  2. همه راس‌ها را به عنوان عنصر‌های مجزا مقداردهی کن.
  3. درخت پوشای کمینه را به عنوان empty مقداردهی اولیه کن.
  4. در حالیکه بیش از یک عنصر وجود دارد، برای هر عنصر، اقدامات زیر را انجام بده:
    1. یالی با نزدیک‌ترین وزن که این عنصر را به سایر عناصر متصل می‌کند، پیدا کن.
    2. این نزدیک یال را در صورتی که تاکنون به درخت پوشای کمینه اضافه نشده، اضافه کن.
  5. درخت پوشای کمینه را بازگردان.

در ادامه، ایده نهفته در پس الگوریتم بروکا، همراه با مثال نمایش داده شده است. شایان ذکر است که ایده این الگوریتم، مانند الگوریتم «درخت پوشای کمینه» (Minimum Spanning Tree) پریم است. منظور از درخت پوشای کمینه آن است که همه راس‌ها متصل باشند. بنابراین، دور زیرمجموعه غیرمتصل (که در بالا تشریح شده است) از راس‌ها باید متصل باشند تا یک درخت پوشا ساخته شود. همچنین، آن‌ها باید با یال دارای حداقل وزن متصل شوند تا از آن یک درخت پوشای کمینه بسازند. در ادامه، مفهوم این الگوریتم با استفاده از مثالی، بیان می‌شود.

الگوریتم بروکا (Boruvka’s Algorithm) -- راهنمای کاربردی

به طور اولیه، MST خالی است. هر راسی یک عنصر مجرد است که با خط آبی در تصویر زیر مشخص شده است.

الگوریتم بروکا (Boruvka’s Algorithm) -- راهنمای کاربردی

برای هر عنصر، کم‌وزن‌ترین یالی که آن را به دیگر عنصر‌ها متصل می‌کند، یافت می‌شود.

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

سبک‌ترین یال‌ها با رنگ سبز مشخص شده‌اند. اکنون، درخت پوشای کمینه به صورت 01,28,23,34,56,67{0-1, 2-8, 2-3, 3-4, 5-6, 6-7}‎ است.

الگوریتم بروکا (Boruvka’s Algorithm) -- راهنمای کاربردی

پس از مراحل بالا، عنصر‌ها 0,1,2,3,4,8,5,6,7{{0,1}, {2,3,4,8}, {5,6,7}} هستند. این عنصر‌ها با دوایر آبی رنگ مشخص شده‌اند.

الگوریتم بروکا (Boruvka’s Algorithm) -- راهنمای کاربردی

اکنون، مجددا مراحل تکرار می‌شوند. برای هر عنصر، سبک‌ترین یالی که آن را به دیگر عنصر‌ها متصل می‌کند، پیدا می‌شود.

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

سبک‌ترین یال‌ها با رنگ سبز مشخص شده‌اند. اکنون، درخت پوشای کمینه به صورت 01,28,23,34,56,67,12,25{0-1, 2-8, 2-3, 3-4, 5-6, 6-7, 1-2, 2-5}‎ است.

الگوریتم بروکا (Boruvka’s Algorithm) -- راهنمای کاربردی

در این گام، تنها یک عنصر {0, 1, 2, 3, 4, 5, 6, 7, 8}‎ وجود دارد که همه یال‌ها را دربر می‌گیرد. با توجه به اینکه تنها یک عنصر باقی مانده است، کار متوقف و درخت پوشای کمینه بازگردانده می‌شود. در ادامه، پیاده‌سازی الگوریتم بروکا در زبان‌های برنامه‌نویسی C++/C و پایتون انجام شده است.

پیاده‌سازی الگوریتم بروکا در C++/C

1// Boruvka's algorithm to find Minimum Spanning 
2// Tree of a given connected, undirected and 
3// weighted graph 
4#include <stdio.h> 
5  
6// a structure to represent a weighted edge in graph 
7struct Edge 
8{ 
9    int src, dest, weight; 
10}; 
11  
12// a structure to represent a connected, undirected 
13// and weighted graph as a collection of edges. 
14struct Graph 
15{ 
16    // V-> Number of vertices, E-> Number of edges 
17    int V, E; 
18  
19    // graph is represented as an array of edges. 
20    // Since the graph is undirected, the edge 
21    // from src to dest is also edge from dest 
22    // to src. Both are counted as 1 edge here. 
23    Edge* edge; 
24}; 
25  
26// A structure to represent a subset for union-find 
27struct subset 
28{ 
29    int parent; 
30    int rank; 
31}; 
32  
33// Function prototypes for union-find (These functions are defined 
34// after boruvkaMST() ) 
35int find(struct subset subsets[], int i); 
36void Union(struct subset subsets[], int x, int y); 
37  
38// The main function for MST using Boruvka's algorithm 
39void boruvkaMST(struct Graph* graph) 
40{ 
41    // Get data of given graph 
42    int V = graph->V, E = graph->E; 
43    Edge *edge = graph->edge; 
44  
45    // Allocate memory for creating V subsets. 
46    struct subset *subsets = new subset[V]; 
47  
48    // An array to store index of the cheapest edge of 
49    // subset.  The stored index for indexing array 'edge[]' 
50    int *cheapest = new int[V]; 
51  
52    // Create V subsets with single elements 
53    for (int v = 0; v < V; ++v) 
54    { 
55        subsets[v].parent = v; 
56        subsets[v].rank = 0; 
57        cheapest[v] = -1; 
58    } 
59  
60    // Initially there are V different trees. 
61    // Finally there will be one tree that will be MST 
62    int numTrees = V; 
63    int MSTweight = 0; 
64  
65    // Keep combining components (or sets) until all 
66    // compnentes are not combined into single MST. 
67    while (numTrees > 1) 
68    { 
69         // Everytime initialize cheapest array 
70          for (int v = 0; v < V; ++v) 
71           { 
72               cheapest[v] = -1; 
73           } 
74  
75        // Traverse through all edges and update 
76        // cheapest of every component 
77        for (int i=0; i<E; i++) 
78        { 
79            // Find components (or sets) of two corners 
80            // of current edge 
81            int set1 = find(subsets, edge[i].src); 
82            int set2 = find(subsets, edge[i].dest); 
83  
84            // If two corners of current edge belong to 
85            // same set, ignore current edge 
86            if (set1 == set2) 
87                continue; 
88  
89            // Else check if current edge is closer to previous 
90            // cheapest edges of set1 and set2 
91            else
92            { 
93               if (cheapest[set1] == -1 || 
94                   edge[cheapest[set1]].weight > edge[i].weight) 
95                 cheapest[set1] = i; 
96  
97               if (cheapest[set2] == -1 || 
98                   edge[cheapest[set2]].weight > edge[i].weight) 
99                 cheapest[set2] = i; 
100            } 
101        } 
102  
103        // Consider the above picked cheapest edges and add them 
104        // to MST 
105        for (int i=0; i<V; i++) 
106        { 
107            // Check if cheapest for current set exists 
108            if (cheapest[i] != -1) 
109            { 
110                int set1 = find(subsets, edge[cheapest[i]].src); 
111                int set2 = find(subsets, edge[cheapest[i]].dest); 
112  
113                if (set1 == set2) 
114                    continue; 
115                MSTweight += edge[cheapest[i]].weight; 
116                printf("Edge %d-%d included in MST\n", 
117                       edge[cheapest[i]].src, edge[cheapest[i]].dest); 
118  
119                // Do a union of set1 and set2 and decrease number 
120                // of trees 
121                Union(subsets, set1, set2); 
122                numTrees--; 
123            } 
124        } 
125    } 
126  
127    printf("Weight of MST is %d\n", MSTweight); 
128    return; 
129} 
130  
131// Creates a graph with V vertices and E edges 
132struct Graph* createGraph(int V, int E) 
133{ 
134    Graph* graph = new Graph; 
135    graph->V = V; 
136    graph->E = E; 
137    graph->edge = new Edge[E]; 
138    return graph; 
139} 
140  
141// A utility function to find set of an element i 
142// (uses path compression technique) 
143int find(struct subset subsets[], int i) 
144{ 
145    // find root and make root as parent of i 
146    // (path compression) 
147    if (subsets[i].parent != i) 
148      subsets[i].parent = 
149             find(subsets, subsets[i].parent); 
150  
151    return subsets[i].parent; 
152} 
153  
154// A function that does union of two sets of x and y 
155// (uses union by rank) 
156void Union(struct subset subsets[], int x, int y) 
157{ 
158    int xroot = find(subsets, x); 
159    int yroot = find(subsets, y); 
160  
161    // Attach smaller rank tree under root of high 
162    // rank tree (Union by Rank) 
163    if (subsets[xroot].rank < subsets[yroot].rank) 
164        subsets[xroot].parent = yroot; 
165    else if (subsets[xroot].rank > subsets[yroot].rank) 
166        subsets[yroot].parent = xroot; 
167  
168    // If ranks are same, then make one as root and 
169    // increment its rank by one 
170    else
171    { 
172        subsets[yroot].parent = xroot; 
173        subsets[xroot].rank++; 
174    } 
175} 
176  
177// Driver program to test above functions 
178int main() 
179{ 
180    /* Let us create following weighted graph 
181             10 
182        0--------1 
183        |  \     | 
184       6|   5\   |15 
185        |      \ | 
186        2--------3 
187            4       */
188    int V = 4;  // Number of vertices in graph 
189    int E = 5;  // Number of edges in graph 
190    struct Graph* graph = createGraph(V, E); 
191  
192  
193    // add edge 0-1 
194    graph->edge[0].src = 0; 
195    graph->edge[0].dest = 1; 
196    graph->edge[0].weight = 10; 
197  
198    // add edge 0-2 
199    graph->edge[1].src = 0; 
200    graph->edge[1].dest = 2; 
201    graph->edge[1].weight = 6; 
202  
203    // add edge 0-3 
204    graph->edge[2].src = 0; 
205    graph->edge[2].dest = 3; 
206    graph->edge[2].weight = 5; 
207  
208    // add edge 1-3 
209    graph->edge[3].src = 1; 
210    graph->edge[3].dest = 3; 
211    graph->edge[3].weight = 15; 
212  
213    // add edge 2-3 
214    graph->edge[4].src = 2; 
215    graph->edge[4].dest = 3; 
216    graph->edge[4].weight = 4; 
217  
218    boruvkaMST(graph); 
219  
220    return 0; 
221} 
222  
223// Thanks to Anukul Chand for modifying above code.

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

1# Boruvka's algorithm to find Minimum Spanning 
2# Tree of a given connected, undirected and weighted graph 
3  
4from collections import defaultdict 
5  
6#Class to represent a graph 
7class Graph: 
8  
9    def __init__(self,vertices): 
10        self.V= vertices #No. of vertices 
11        self.graph = [] # default dictionary to store graph 
12          
13   
14    # function to add an edge to graph 
15    def addEdge(self,u,v,w): 
16        self.graph.append([u,v,w]) 
17  
18    # A utility function to find set of an element i 
19    # (uses path compression technique) 
20    def find(self, parent, i): 
21        if parent[i] == i: 
22            return i 
23        return self.find(parent, parent[i]) 
24  
25    # A function that does union of two sets of x and y 
26    # (uses union by rank) 
27    def union(self, parent, rank, x, y): 
28        xroot = self.find(parent, x) 
29        yroot = self.find(parent, y) 
30  
31        # Attach smaller rank tree under root of high rank tree 
32        # (Union by Rank) 
33        if rank[xroot] < rank[yroot]: 
34            parent[xroot] = yroot 
35        elif rank[xroot] > rank[yroot]: 
36            parent[yroot] = xroot 
37        #If ranks are same, then make one as root and increment 
38        # its rank by one 
39        else : 
40            parent[yroot] = xroot 
41            rank[xroot] += 1
42  
43    # The main function to construct MST using Kruskal's algorithm 
44    def boruvkaMST(self): 
45        parent = []; rank = [];  
46  
47        # An array to store index of the cheapest edge of 
48        # subset. It store [u,v,w] for each component 
49        cheapest =[] 
50  
51        # Initially there are V different trees. 
52        # Finally there will be one tree that will be MST 
53        numTrees = self.V 
54        MSTweight = 0
55  
56        # Create V subsets with single elements 
57        for node in range(self.V): 
58            parent.append(node) 
59            rank.append(0) 
60            cheapest =[-1] * self.V 
61      
62        # Keep combining components (or sets) until all 
63        # compnentes are not combined into single MST 
64  
65        while numTrees > 1: 
66  
67            # Traverse through all edges and update 
68               # cheapest of every component 
69            for i in range(len(self.graph)): 
70  
71                # Find components (or sets) of two corners 
72                # of current edge 
73                u,v,w =  self.graph[i] 
74                set1 = self.find(parent, u) 
75                set2 = self.find(parent ,v) 
76  
77                # If two corners of current edge belong to 
78                # same set, ignore current edge. Else check if  
79                # current edge is closer to previous 
80                # cheapest edges of set1 and set2 
81                if set1 != set2:      
82                      
83                    if cheapest[set1] == -1 or cheapest[set1][2] > w : 
84                        cheapest[set1] = [u,v,w]  
85  
86                    if cheapest[set2] == -1 or cheapest[set2][2] > w : 
87                        cheapest[set2] = [u,v,w] 
88  
89            # Consider the above picked cheapest edges and add them 
90            # to MST 
91            for node in range(self.V): 
92  
93                #Check if cheapest for current set exists 
94                if cheapest[node] != -1: 
95                    u,v,w = cheapest[node] 
96                    set1 = self.find(parent, u) 
97                    set2 = self.find(parent ,v) 
98  
99                    if set1 != set2 : 
100                        MSTweight += w 
101                        self.union(parent, rank, set1, set2) 
102                        print ("Edge %d-%d with weight %d included in MST" % (u,v,w)) 
103                        numTrees = numTrees - 1
104              
105            #reset cheapest array 
106            cheapest =[-1] * self.V 
107  
108              
109        print ("Weight of MST is %d" % MSTweight) 
110                            
111  
112      
113g = Graph(4) 
114g.addEdge(0, 1, 10) 
115g.addEdge(0, 2, 6) 
116g.addEdge(0, 3, 5) 
117g.addEdge(1, 3, 15) 
118g.addEdge(2, 3, 4) 
119  
120g.boruvkaMST() 
121  
122#This code is contributed by Neelam Yadav 

خروجی قطعه کد بالا، به صورت زیر است.

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

پیچیدگی زمانی الگوریتم بروکا از درجه O(E log V)‎ و در واقع، مشابه با پیچیدگی الگوریتم کراسکال و پریم است. الگوریتم بروکا یکی از قدیمی‌ترین الگوریتم‌های «درخت پوشای کمینه» (Minimum Spanning Tree) است که در سال ۱۹۲۶ میلادی، مدت‌ها پیش از اینکه کامپیوترها حتی وجود داشته باشند، توسط بورکا کشف شده است. این الگوریتم به عنوان روشی برای ساخت شبکه الکتریسیته موثر، معرفی شده بود.

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

^^

بر اساس رای ۰ نفر
آیا این مطلب برای شما مفید بود؟
اگر بازخوردی درباره این مطلب دارید یا پرسشی دارید که بدون پاسخ مانده است، آن را از طریق بخش نظرات مطرح کنید.
منابع:
GeeksforGeeks
نظر شما چیست؟

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *