Boruvka's algorithm

Question

class Edge
{
public:
    int v1;
    int v2;
    int weight;
};
class Subset
{
public:
    int rank;
    int parent;
};
int find(Subset* subsets,int V)
{
    if(subsets[V].parent!=V)
        subsets[V].parent= find(subsets,subsets[V].parent);
    return subsets[V].parent;
}
void union_rank(Subset* subsets,int x,int y)
{
    if(subsets[x].rank>subsets[y].rank)
        subsets[y].parent=x;
    else   if(subsets[x].rank<subsets[y].rank)
                subsets[x].parent=y;
    else
        {
              subsets[y].parent=x;
              subsets[x].rank++;
        }
}
void boruvka(Edge* list,int V,int E)
{
    Subset* subsets=new Subset[V];
int *cheapest = new int[V];
for(int i=0;i<V;i++)
{
    subsets[i].parent=i;
    subsets[i].rank=0;
     cheapest[V] = -1;
}
    int numTrees = V;
    int MSTweight = 0;
    while (numTrees > 1)
    {
          for (int v = 0; v < V; v++)
           {
               cheapest[v] = -1;
           }
        for (int i=0; i<E; i++)
        {
            int x = find(subsets, list[i].v1);
            int y = find(subsets, list[i].v2);
            if (x!=y)
             {
               if (cheapest[x] == -1 || list[cheapest[x]].weight > list[i].weight)
                 cheapest[x] = i;

               if (cheapest[y] == -1 ||list[cheapest[y]].weight > list[i].weight)
                 cheapest[y] = i;
            }
        }
        for (int i=0; i<V; i++)
        {
            if (cheapest[i] != -1)
            {
                int x = find(subsets, list[i].v1);
                int y = find(subsets, list[i].v2);

                if (x==y)
                    continue;
                MSTweight += list[cheapest[i]].weight;
                cout<<list[cheapest[i]].v1<<" "<<list[cheapest[i]].v2<<" "<<list[cheapest[i]].weight<<endl;

                union_rank(subsets, x, y);
                numTrees--;
            }
        }
    }

    printf("Weight of MST is %d\n", MSTweight);
    return;
}
int main()
{
int V, E, tempX, tempY,wt;
cin >>V>>E;
Edge* list=new Edge[E];
for(int i=0;i<E;i++)
{
    cin>>tempX>>tempY>>wt;
    list[i].v1=tempX;
    list[i].v2=tempY;
    list[i].weight=wt;
}
//sort(list,list+E,comp);
boruvka(list,V,E);
    return 0;
}

My algorithm keeps going into infinite loop for bigger graphs can someone help me resolve it?I worked for ver small graphs but anything similar to this graph it goes into infinite loop.I checked the value of numTree and it stops decreasing after a certain value I'm not sure why. This is the graph I checked with:

14 20
    0 1 1
    0 2 2
    0 7 3
    1 2 4
    1 3 5
    2 5 6
    3 4 7
    3 10 8
    4 5 9
    4 6 10
    5 9 11
    5 12 12
    6 7 13
    7 8 14
    8 9 15
    8 13 16
    10 11 17
    10 13 18
    11 12 19
    12 13 20

Answer 1

The problem lies in this for loop

        for (int i=0; i<V; i++)
        {
            if (cheapest[i] != -1)
            {
                int x = find(subsets, list[i].v1);
                int y = find(subsets, list[i].v2);

                if (x==y)
                    continue;
                MSTweight += list[cheapest[i]].weight;
                cout<<list[cheapest[i]].v1<<" "<<list[cheapest[i]].v2<<" "<<list[cheapest[i]].weight<<endl;

                union_rank(subsets, x, y);
                numTrees--;
            }
        }

You're iterating over the vertices here i=0..V-1 but you're accessing the list of edges inside the loop list[i] which is incorrect.

Instead you should change the for loop to iterate over the edges i=0..E-1 and change the body of the loop to the following:

int x = find(subsets, list[i].v1);
int y = find(subsets, list[i].v2);
if (x==y)
  continue;
if (cheapest[x] == list[i].weight || cheapest[y] == list[i].weight) { // this checks if the given edge is the cheapest from the tree containing x or the tree containing y
  MSTweight += list[cheapest[i]].weight;
  union_rank(subsets, x, y);
  union_rank(subsets, x, y);
}