Greedy Algorithms | Set 9 (Boruvka's algorithm) - GeeksforGeeks
Like Prim's and Kruskal's, Boruvka's algorithm is also a Greedy algorithm. Below is complete algorithm.
A spanning tree means all vertices must be connected. So the two disjoint subsets (discussed above) of vertices must be connected to make a Spanning Tree. And they must be connected with the minimum weight edge to make it a Minimum Spanning Tree.
http://algs4.cs.princeton.edu/43mst/BoruvkaMST.java.html
https://github.com/sbiyyala/Algorithms/blob/master/src/BoruvkaMST.java
http://algos.org/borukvas-mstminimum-spanning-tree-java/
Read full article from Greedy Algorithms | Set 9 (Boruvka's algorithm) - GeeksforGeeks
Like Prim's and Kruskal's, Boruvka's algorithm is also a Greedy algorithm. Below is complete algorithm.
1) Input is a connected, weighted and directed graph.
2) Initialize all vertices as individual components (or sets).
3) Initialize MST as empty.
4) While there are more than one components, do following
for each component.
a) Find the closest weight edge that connects this
component to any other component.
b) Add this closest edge to MST if not already added.
5) Return MST.
A spanning tree means all vertices must be connected. So the two disjoint subsets (discussed above) of vertices must be connected to make a Spanning Tree. And they must be connected with the minimum weight edge to make it a Minimum Spanning Tree.
// The main function for MST using Boruvka's algorithmvoid boruvkaMST(struct Graph* graph){ // Get data of given graph int V = graph->V, E = graph->E; Edge *edge = graph->edge; // Allocate memory for creating V subsets. struct subset *subsets = new subset[V]; // An array to store index of the cheapest edge of // subset. The stored index for indexing array 'edge[]' int *cheapest = new int[V]; // Create V subsets with single elements for (int v = 0; v < V; ++v) { subsets[v].parent = v; subsets[v].rank = 0; cheapest[v] = -1; } // Initially there are V different trees. // Finally there will be one tree that will be MST int numTrees = V; int MSTweight = 0; // Keep combining components (or sets) until all // compnentes are not combined into single MST. while (numTrees > 1) { // Traverse through all edges and update // cheapest of every component for (int i=0; i<E; i++) { // Find components (or sets) of two corners // of current edge int set1 = find(subsets, edge[i].src); int set2 = find(subsets, edge[i].dest); // If two corners of current edge belong to // same set, ignore current edge if (set1 == set2) continue; // Else check if current edge is closer to previous // cheapest edges of set1 and set2 else { if (cheapest[set1] == -1 || edge[cheapest[set1]].weight > edge[i].weight) cheapest[set1] = i; if (cheapest[set1] == -1 || edge[cheapest[set2]].weight > edge[i].weight) cheapest[set2] = i; } } // Consider the above picked cheapest edges and add them // to MST for (int i=0; i<V; i++) { // Check if cheapest for current set exists if (cheapest[i] != -1) { int set1 = find(subsets, edge[cheapest[i]].src); int set2 = find(subsets, edge[cheapest[i]].dest); if (set1 == set2) continue; MSTweight += edge[cheapest[i]].weight; printf("Edge %d-%d included in MST\n", edge[cheapest[i]].src, edge[cheapest[i]].dest, edge[cheapest[i]].weight); // Do a union of set1 and set2 and decrease number // of trees Union(subsets, set1, set2); numTrees--; } } } printf("Weight of MST is %d\n", MSTweight); return;}http://algs4.cs.princeton.edu/43mst/BoruvkaMST.java.html
https://github.com/sbiyyala/Algorithms/blob/master/src/BoruvkaMST.java
http://algos.org/borukvas-mstminimum-spanning-tree-java/
Read full article from Greedy Algorithms | Set 9 (Boruvka's algorithm) - GeeksforGeeks
