Boruvka 算法

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;
}

对于更大的图，我的算法一直进入无限循环有人可以帮我解决这个问题吗？我为非常小的图工作，但任何与此图类似的东西都会进入无限循环loop.I 检查了 numTree 的值，它在某个值后停止减少我不确定为什么。这是我检查过的图表：

Answer 1

问题出在这个for循环


        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--;
            }
        }

您在此处迭代顶点 i=0..V-1 但您正在访问循环内的边列表 list[i] 这是不正确的。

相反，您应该将 for 循环更改为遍历边缘 i=0..E-1 并将循环主体更改为以下内容：

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);
}

Boruvka 算法

Boruvka's algorithm

c++

algorithm

greedy

minimum-spanning-tree