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
7 struct 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.
14 struct 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
27 struct subset
28 {
29 int parent;
30 int rank;
31 };
32
33 // Function prototypes for union-find (These functions are defined
34 // after boruvkaMST() )
35 int find(struct subset subsets[], int i);
36 void Union(struct subset subsets[], int x, int y);
37
38 // The main function for MST using Boruvka's algorithm
39 void 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
132 struct 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)
143 int 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)
156 void 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
178 int 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.
$g++ -std=c++11 -o main *.cpp
$main
Edge 0-3 included in MST
Edge 0-1 included in MST
Edge 2-3 included in MST
Weight of MST is 19