Union Find to solve Traveling Salesman

Question

I have to use the union find algorithm to solve the traveling salesman problem. I prettymuch got it done except for one problem I've just discovered. As it processes each edge, it will check for a cycle, which is done with the whole parent array thing. The problem is that, when it gets to the last edge I need to add to complete the problem, since it is technically a cycle, it does not add the edge, so the path can not be completed. How can I differentiate a useless cycle from the cycle indiicating that we are done?

Here's the code I got so far

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

Here are the edges it goes through in order

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,

Answer 1

What about keeping track of the size of each of the sets?

Then, when doing a union, if the root of both is the same (i.e. a cycle) and the root's size equals the sum of all the points in your problem, include that edge and stop, otherwise continue as per usual.

Warning:

Note that a simple Union-Find implementation is likely to end you up with minimum spanning tree rather than a hamiltonian cycle. You need to make sure you pick appropriate edges - I'll assume you've figured that out, or, if not, I'll leave it to you.

Elaboration:

The Union for your problem should look something like: (derived from Wikipedia)
(returning false or true to indicate whether we should add the edge)

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

(the proper merge (for efficiency) is a little more complicated - you should compare the depths and pick the deepest one as the parent, see Wikipedia for details)

Now, my suggestion:

Create a size variable for each node, initialized to 1, and then the Union function:

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

Example:

Points:

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

There are 4 points, thus pointCount = 4

Starting off: (size appears under node)

1  2  3  4
1  1  1  1

Union 1 and 2:

1  3  4
2  1  1
|
2
1

Union 3 and 2:

3  4
3  1
|
1
2
|
2
1

Union 3 and 1:

The common root is 3 (thus xRoot == yRoot is true) and xRoot.size(3) != pointCount(4), thus we return false (don't add the edge).

Union 3 and 4:

4
4
|
3
3
|
1
2
|
2
1

Union 4 and 1:

The common root is 4 (thus xRoot == yRoot is true) and xRoot.size(4) == pointCount(4), thus we return true (add the edge) and we set the flag to indicate that we're done.