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