Boruvka's Algorirthm in C

boruvka.md

Boruvka's Algorithm

Boruvka's Algorithm is a minimum spanning tree algorithm.

What's a spanning tree? In a graph (all this is about graphs), the path which covers all the nodes is called the spanning tree. Why tree? Because if a graph contains n nodes, a spanning tree contains n-1 nodes which is a property of a tree.

What's a minimum spanning tree? A graph might contain lot of spanning trees, but the one which takes the minimum total weight to travel is called the minimum spanning tree

So, Boruvka's works by using a concept called Disjoint Sets. ( Which btw, is also used in Kruskal ).

What are Disjoint Sets? Sets are data structure which resembles sets that we learned in Math. Disjoint Sets are sets which don't have any element in common. Geddit?

For example, {1}, {2, 3, 5}, {4, 6}

Operations on Disjoint Sets:

• find(x): when passed an element x, returns a reference set containing the element x.
• union(x, y): when passed two elements x and y, finds the set containing the elements and merges them both into one set and returns it's reference.

So how does Boruvka's algorithm work?

1. Given a graph G with V vertices
2. Makes V vertices into V sets and store it into components
3. Creates an empty MST array ( to store the Minimum Spanning Path )
4. while ( components > 1)
   1. loop through all the edges connecting this vertice to others
   2. find the edge uv with the minimum weight
   3. union the vertices which the edge connects (u & v)
   4. add that edge to the MST array ( if it's not there already )

print MST

Code using C and Adjacency Matrix:

#include <stdio.h>
struct Edge
{
  int src, dest, weight;
};
struct Graph
{
  int V, E;
  Edge* edge;
};

int G[10][10];

struct subset
{
  int parent;
  int rank;
};

int find(struct subset subsets[], int i);

void Union(struct subset subsets[], int x, int y);

Edge* make_edges(int graph[10][10], int V, int E);

void boruvkaMST(int graph[10][10], int V, int E)
{
  // We create a new edges structure 
  // from the adjanceny matrix
  Edge* edge = make_edges(graph, V, E);
  struct subset *subsets = new subset[V];
  int *cheapest = new int[V];
  
  for (int v = 0; v < V; ++v)
  {
    subsets[v].parent = v;
    subsets[v].rank = 0;
    cheapest[v] = -1;
  }

  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
  
        Union(subsets, set1, set2);
        numTrees--;
      }
    }
  }

  printf("Weight of MST is %d\n", MSTweight);
  return;
}

// A utility function to find set of an element i
// (uses path compression technique)
int find(struct subset subsets[], int i)
{
  // find root and make root as parent of i
  // (path compression)
  if (subsets[i].parent != i)
  subsets[i].parent =
      find(subsets, subsets[i].parent);

  return subsets[i].parent;
}

// A function that does union of two sets of x and y
// (uses union by rank)
void Union(struct subset subsets[], int x, int y)
{
  int xroot = find(subsets, x);
  int yroot = find(subsets, y);

  // Attach smaller rank tree under root of high
  // rank tree (Union by Rank)
  if (subsets[xroot].rank < subsets[yroot].rank)
    subsets[xroot].parent = yroot;
  else if (subsets[xroot].rank > subsets[yroot].rank)
    subsets[yroot].parent = xroot;

  // If ranks are same, then make one as root and
  // increment its rank by one
  else
  {
    subsets[yroot].parent = xroot;
    subsets[xroot].rank++;
  }
}

Edge* make_edges(int graph[10][10], int V, int E){
  Edge *edge;
  edge = new Edge[E];
  int c = 0;
  for(int i=0; i<V; i++){
    for(int j=0; j<V; j++){
      if(graph[i][j]>0 && graph[i][j]<999){
        edge[c].src = i;
        edge[c].dest = j;
        edge[c].weight = graph[i][j];
        c++;
      }
    }
  }
  return edge;
}

void take_input(int V){
  int i,j;
  cout<<"Enter the adjanceny matrix of the graph\n"<<endl;
  cout<<"   ";
  for(i=0;i<V;i++)
    cout<<i<<"  ";
  cout<<endl;
  for(i=0;i<V;i++){
    cout<<i<<" ";
    for(j=0;j<V;j++)
      cin>>G[i][j];
  }
}

int main()
{
  int V, E;
  cout<<"Enter the number of vertices and Edges: ";
  cin>>V>>E;
  take_input(V);
  boruvkaMST(G, V, E);
  return 0;
}