java - 实现并查算法混淆

Question

我正在尝试为 Kruskal 实现并查找算法。我正在使用这个伪代码，我不明白下面的联合部分步骤2(它不是递归调用)或者我是否很接近。如果这种方法不起作用，我可以使用任何我理解的实现。提前致谢。 U 和 V 是我的边缘节点，目前只是整数。

  Init(V)
  1.for every vertex v do
  2.boss[v]=v
  3.size[v]=1
  4.set[v]={v}

  Find (u)
  1.Return boss[u] 

  Union (u,v)
  1.if size[boss[u]]>size[boss[v]] then
  2.set[boss[u]]=set[boss[u]] union set[boss[v]]
  3.size[boss[u]]+=size[boss[v]]
  4.for every z in set[boss[v]] do
  5.boss[z]=boss[u]
  6.else do steps 2.-5. with u,v switched

我不明白第 2 步，这是迄今为止我的代码:

public class UnionFind {

    private int[] _boss;
    private int[] _size;
    private int[] _set;

    public UnionFind(int max) 
    {
        _boss = new int[max];
        _size = new int[max];
        _set  = new int[max];
    }

    public void init(Set<Integer> vertSet)
    {
        //for every vertex do
        int j=0;
        for(int i : vertSet)
        {
            _boss[j]=i;
            _size[j]=1;
            _set[j]=i;
            j++;
        }
    }

    int find(int u)
    {
        return(_boss[u]);
    }

    void union(int u, int v)
    {
        if(_size[_boss[u]]>_size[_boss[v]])
        {
            _set[_boss[u]]=_set[_boss[u]];
             //_set[_boss[v]];
            _size[_boss[u]]+=_size[_boss[v]];

            for(int z=0;z<_boss.length;z++)
            {
                _boss[z]=_boss[u];
            }
        }
        else
        {
            //switch u and v
            _set[_boss[v]]=_set[_boss[v]];
            //union(_set[_boss[v]],_set[_boss[u]]);
            _size[_boss[v]]+=_size[_boss[u]];

            for(int z=0;z<_boss.length;z++)
            {
                _boss[z]=_boss[v];
            }
        }
    }

Answer 1

第 2 步意味着集合 u 现在成为 u 和 v 的并集，因此您不能指定 set[v] = set[v] (u 和 v 是 boss[u]、boss[v] 的缩写，分别)。所以，如果集合 u 是 {u} 且集合 v 是 {v}，那么经过这一步，集合 u 将是 {u,v}，再一个例子是 set u = {1,2} ，set v = {3, 4}，因此在此之后，设置 u = {1,2,3,4}。根据您使用的数据结构，您需要以不同的方式实现它。一种方法是使用 ArrayList

ArrayList<Integer> set[] = new ArrayList[max];
//Initialize each set, add element into set
for(int i = 0; i < max; i++)
   set[i] = new ArrayList();
   set[i].add(i);
//For step 2
set[boss[u]].addAll(set[boss[v]]);

最后一件事是，你的步骤 4 是错误的，对于你当前的实现，你只需将每个元素添加到 set[boss[u]] 中，但在这一步中，它们只需要 set[boss[ 中的元素v]]。所以:

        int bossV = boss[v];//This is important! Answer why this is needed by yourself.
        for(int z=0;z<_boss.length;z++)
        {
            if(boss[z] == bossV)
               _boss[z]=_boss[u];
        }

小通知:您使用的这个版本不是 union-find 最快的版本，请尝试阅读更多相关信息!