## 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 edges= new LinkedList(); ItemNode parendNode = null; } ```

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.

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