Boruvka's algorithm is one of the earliest algorithms for finding the Minimum Spanning Tree (MST) of a connected, undirected graph. Developed by the Czech mathematician Otakar Borůvka in 1926, this algorithm uses a greedy approach and is particularly efficient for parallel processing.

• Goal: Connect all vertices in the graph with the minimum total edge weight without forming cycles.
• Process:
  • Initialize each vertex as a separate component: Start with each vertex as its own component.
  • Iteratively merge components: In each iteration, find the smallest edge for each component and add it to the MST. This step reduces the number of components by merging them.
• Parallel Processing: The algorithm is suitable for parallel processing since each component can independently find its smallest connecting edge.
• Greedy Approach: Like Kruskal’s and Prim’s algorithms, Boruvka’s algorithm also follows a greedy strategy by selecting the smallest edges to connect components.

Overall, Boruvka’s algorithm is an effective method for constructing the MST, especially in cases where parallel processing can be leveraged. It repeatedly reduces the number of components until a single connected component, the MST, is obtained.

Step-by-Step Algorithm

1. Initialization:

   • Create an array subsets to represent subsets for union-find, where each vertex is initially its own parent.
   • Create an array cheapest to keep track of the cheapest edge for each component, initialized to -1.
   • Set the initial number of components (numTrees) to the number of vertices.
   • Initialize the total weight of the MST (MSTweight) to 0.

2. Repeat until there is only one component (tree):

   • Step 2.1: Traverse all edges to update the cheapest array for each component:

     • For each edge (u, v) with weight w:
       • Find the root of the component containing vertex u using the union-find find operation.
       • Find the root of the component containing vertex v using the union-find find operation.
       • If u and v belong to different components:
         • If cheapest[root_u] is -1 or the weight of the current edge is less than the weight of the edge currently stored in cheapest[root_u], update cheapest[root_u] to the index of the current edge.
         • Similarly, update cheapest[root_v] if needed.

   • Step 2.2: Add the cheapest edges to the MST and merge components:

     • For each vertex i from 0 to V-1:
       • If cheapest[i] is not -1 (i.e., there is a valid edge):
         • Find the roots of the components containing the endpoints of the edge stored in cheapest[i].
         • If the components are different, add the edge to the MST, perform the union operation to merge the components, and update the total MST weight.
         • Decrease the number of components (numTrees) by 1.

   • Step 2.3: Reset the cheapest array for the next iteration by setting all entries to -1.

3. Output:

   • Print the edges included in the MST.
   • Print the total weight of the MST.

Algorithm Walkthrough

Consider the example used in the code with the following edges and weights:

Edges: (0-1, 0-2, 0-3, 1-3, 2-3)
Weights: 10, 6, 5, 15, 4
Vertices: 4 (0, 1, 2, 3)

1. Initialize:

   Subsets: [Subset(0, 0), Subset(1, 0), Subset(2, 0), Subset(3, 0)]
   Cheapest: [-1, -1, -1, -1]
   NumTrees: 4
   MSTweight: 0
   

2. First Iteration:

   • Traverse edges:

     (0-1, 10): Cheapest[0] = 0, Cheapest[1] = 0
     (0-2, 6): Cheapest[0] = 1, Cheapest[2] = 1
     (0-3, 5): Cheapest[0] = 2, Cheapest[3] = 2
     (1-3, 15): No update (10 > 5)
     (2-3, 4): Cheapest[2] = 4, Cheapest[3] = 4
     

   • Add cheapest edges:

     (0-3, 5): MSTweight = 5, NumTrees = 3, Union(0, 3)
     (2-3, 4): MSTweight = 9, NumTrees = 2, Union(2, 0)
     

   • Reset cheapest:

     Cheapest: [-1, -1, -1, -1]
     

3. Second Iteration:

   • Traverse edges:

     (0-1, 10): Cheapest[0] = 0, Cheapest[1] = 0
     (0-2, 6): No update (6 > 4)
     (0-3, 5): No update (5 > 4)
     (1-3, 15): No update (15 > 4)
     (2-3, 4): No update (4 > 4)
     

   • Add cheapest edges:

     (0-1, 10): MSTweight = 19, NumTrees = 1, Union(0, 1)
     

   • Reset cheapest:

     Cheapest: [-1, -1, -1, -1]
     

4. Final MST:

   Edges: (0-3, 5), (2-3, 4), (0-1, 10)
   MST Weight: 19
   

Code