algorithm - 工会发现解决旅行推销员

我必须使用联合查找算法来解决旅行商问题除了我刚发现的一个问题外，我都做了。当它处理每一条边时，它将检查一个循环，这是用整个父数组完成的。问题是，当它到达最后一条边时，我需要添加来完成问题，因为它在技术上是一个循环，它不会添加边，所以路径无法完成我如何区分一个无用的循环和指示我们已经完成的循环？
这是我到目前为止得到的密码

private int[] parent; //parent of each vertex
private int[] connection; //number of edges coming from a given vertex
private int[] subsize; //size of each subtree
boolean donepath;

public void GreedyAlgo(){
    ArrayList<Edge> newedges = new ArrayList<Edge>();
    for(int i = 0; i<graph.realedge.size();i++){
        if(donepath) break;
        Edge e= graph.realedge.get(i);
        int x = e.in1;
        int y = e.in2;


        if(unionFind(x,y) && !thirdEdge(x,y)){

            newedges.add(e);



        }

        else{

        }

    }
}


 public int findParent(int i){
    if (parent[i] != i)
       return findParent(parent[i]);
    return parent[i];

}

public boolean unionFind(int x, int y){
     int xx = findParent(x);
     int yy = findParent(y);

    if(xx == yy){

            if(subsize[xx]== n){
                donepath = true;
                return true;
            }
            return false;
    }
     else{

        if( subsize[xx] < subsize[yy]){
             parent[xx] = yy;
                              subsize[yy]+=subsize[xx];
         }
        else if( subsize[xx] >  subsize[yy]){
             parent[yy] = xx;  subsize[xx]+=subsize[yy];
         }
         else{
             parent[yy] = xx;
             subsize[xx]+=subsize[yy];
         }
        connection[x]++;
        connection[y]++;

     }


    return true;


}

public boolean makesCycle(int x, int y){
        int xx = findParent(x);
        int yy = findParent(y);

        if(xx == yy){

            return true;
        }

    return false;
}

这是它经过的边缘

0-0,
1-1,
2-2,
3-3,
4-4,
0-4 should get added,
2-3 should get added,
3-2,
4-0,
0-1 should get added,
0-2 ,
0-3,
1-0,
1-4,
2-0,
3-0,
4-1,
1-3 should get added,
3-1,
2-4 should get added......but doesnt,
3-4,
4-2,
4-3,
1-2,
2-1,

最佳答案

记下每一套的尺寸怎么样？
然后，在进行并集时，如果两者的根是相同的（即一个循环），并且根的大小等于问题中所有点的总和，则包含该边并停止，否则照常继续。
警告：
注意，一个简单的union-find实现可能会以minimum spanning tree而不是hamiltonian cycle结束。你需要确定你选择了合适的边缘-我假设你已经弄明白了，否则，我就留给你了。
阐述：
问题的Union应该类似于：（派生自Wikipedia）
（返回false或true以指示是否应添加边）

boolean Union(x, y)
   xRoot = Find(x)
   yRoot = Find(y)
   if xRoot == yRoot
      return false
   // merge xRoot and yRoot
   xRoot.parent = yRoot
   return true

（正确的合并（为了提高效率）要复杂一点——你应该比较深度，选择最深的一个作为父级，详见维基百科）
现在，我的建议是：
为每个节点创建一个size变量，初始化为1，然后使用Union函数：

boolean Union(x, y)
   xRoot = Find(x)
   yRoot = Find(y)

   if xRoot == yRoot
      // check if it's the last node
      if xRoot.size == pointCount
         done = true
         return true
      else
         return false

   // merge xRoot and yRoot
   xRoot.parent = yRoot
   yRoot.size += xRoot.size
   return true

例子：
要点：

1---2
|\  |
| \ |
|  \|
4---3

有4个点，因此pointCount = 4
开始：（size出现在节点下）

1  2  3  4
1  1  1  1

联合1和2：

1  3  4
2  1  1
|
2
1

联合3和2：

3  4
3  1
|
1
2
|
2
1

联合3和1：
公共根是3（因此xRoot == yRoot是真的）并且xRoot.size(3)！=pointCount(4)，因此返回false（不添加边）。
联合3和4：

4
4
|
3
3
|
1
2
|
2
1

联合4和1：
公共根是4（因此xRoot == yRoot是true）和xRoot.size(4)==pointCount(4)，因此我们返回true（添加边）并设置标志以指示完成。