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

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