Thursday, January 8, 2015

Union and Find algorithm in java

Today I wanted to post Kruskal' algorithm .
one day is too short to understand that
because I have to know union and find algorithm in first.
using it we can find whether this would be circle or not if we connect tree and one point.

It was hard to write java but i tried.

Precondition: all items are numbered and unique

refereced by http://www.algorithmist.com/index.php/Union_Find

If you have any question, comment Plz~

if my code is show how stange. reply and discuss

pseudo code is Below

func find( var element )
  while ( element is not the root ) element = element's parent
  return element
end func

func union( var setA, var setB )
  var rootA = find( setA ), rootB = find( setB )
  if ( rootA is equal to rootB ) return
  else
     set rootB as rootA's parent
end func



  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
package mybook;

import java.util.LinkedList;

/**
 * @author ddavid
 *
 */
public class UnionAndFind {
 
 public static void main(String args[]){
  // aSet
  
  ItemNode itemNode4 = new ItemNode();
  itemNode4.isRoot = false;
  itemNode4.number =4;
  
  ItemNode itemNode3 = new ItemNode();
  itemNode3.isRoot = false;
  itemNode3.number =3;
  
  ItemNode itemNode2 = new ItemNode();
  itemNode2.isRoot = false;
  itemNode2.number =2;
  
  
  ItemNode itemNode1 = new ItemNode();
  itemNode1.isRoot = false;
  itemNode1.number =1;
  
  ItemNode itemNode0 = new ItemNode();
  itemNode0.isRoot = true;
  itemNode0.number =0;
  
  
  // parentNode 
  itemNode4.parendNode = itemNode3;
  itemNode3.parendNode = itemNode2;
  itemNode2.parendNode = itemNode0;
  itemNode1.parendNode = itemNode0;
  
  
  itemNode2.edges.add(itemNode3);
  itemNode3.edges.add(itemNode4);
  itemNode0.edges.add(itemNode1);
  itemNode0.edges.add(itemNode2);
  // bSet 
  
  ItemNode itemNode5 = new ItemNode();
  itemNode5.isRoot = false;
  itemNode5.number =5;
  
  ItemNode itemNode6 = new ItemNode();
  itemNode6.isRoot = true;
  itemNode6.number =6;
  
  itemNode5.parendNode = itemNode6;
  itemNode6.edges.add(itemNode5);
  
  UnionAndFind unf = new UnionAndFind();
  
  System.out.println(unf.find(itemNode0).number);
  System.out.println(unf.find(itemNode1).number);
  System.out.println(unf.find(itemNode2).number);
  System.out.println(unf.find(itemNode3).number);
  System.out.println(unf.find(itemNode4).number);
  
  
  System.out.println();
  System.out.println(unf.find(itemNode5).number);
  System.out.println(unf.find(itemNode6).number);
  
  
  unf.union(itemNode4, itemNode5);
  System.out.println("########## after union############");
  
  System.out.println(unf.find(itemNode0).number);
  System.out.println(unf.find(itemNode1).number);
  System.out.println(unf.find(itemNode2).number);
  System.out.println(unf.find(itemNode3).number);
  System.out.println(unf.find(itemNode4).number);
  
  
  System.out.println();
  System.out.println(unf.find(itemNode5).number);
  System.out.println(unf.find(itemNode6).number);
 }
 
 public ItemNode  find(ItemNode node){
  while(node.isRoot == false ){
   node = node.parendNode;
  }
  return node;
 }
 
 public void union(ItemNode a, ItemNode b){
  ItemNode aRootNode = find(a);
  ItemNode bRootNode = find(b);
  
  
  if(aRootNode == bRootNode){
   
  }else{
   aRootNode.isRoot = false;   
   aRootNode.parendNode = bRootNode;
   bRootNode.edges.add(aRootNode);
  }
 }
}

class ItemNode {
 boolean isRoot = false;
 int number = 0;
 LinkedList<ItemNode> edges= new LinkedList<ItemNode>();
 ItemNode parendNode = null; 
}

2 comments:

  1. Nice, one minor observation, you could avoid that empty if statement by inverting the "if" condition:

    if(aRootNode!=bRootNode){
    aRootNode.isRoot = false;
    // .........
    }

    However, what I am missing from this blog post is what are the applications of union-find algorithm, like where can it be used in practice. Would be great to cover that too.

    ReplyDelete
    Replies
    1. Well. Thank you for reading my post.

      as you told me, It will be nice if if(aRootNode == bRootNode){ ---> if(aRootNode!=bRootNode){ because computer have to check and spend time to do nothing.

      like what you sad and I will later update this post with usage in this algorithm.

      anyway thank you

      Delete