UnionFind 알고리즘 설명
HashMap으로 구현
배열로 구현
최종 코드
깃허브
UnionFind 알고리즘 설명
트리, 그래프 구조에서 같은 부모(집합)에 속해 있는지, 사이클이 존재하는지에 대해서 판별 할 수 있는 알고리즘이다.
다시 말해 각각의 노드들에 대한 연결 정보를 알 수 있을때 특정 노드 두개의 연결 여부 및 노드들의 사이클 정보를 판단 할 수 있다.
HashMap으로 구현
정점의 수 만큼 본인의 부모(집합)을 본인으로 초기화
아직 정점들에 대한 정보에 대해 모르기 때문에 본인 스스로를 본인의 부모(집합)으로 설정
사이클 여부도 판별하기 위해 불리언값으로 설정
public class FindCommonParent {
private final HashMap<Integer ,Integer> parentArray;
private boolean hasCycle;
public FindCommonParent(int vertexNumber) {
this.parentArray = new HashMap<>();
this.hasCycle = false;
for(int i = 1; i <= vertexNumber; i++) {
this.parentArray.put(i,i);
}
}
}노드들의 정보가 들어왔을때 노드의 부모 찾기
private int findParent(int child) {
int parent = child;
while (this.parentArray.get(parent) != parent) {
parent = this.parentArray.get(parent);
}
return parent;
}while문을 통해 본인 스스로가 부모(집합)인 경우까지 찾아 올라감
위의 find를 통해 부모를 찾고 다른 부모(집합)일 경우 child의 부모를 parent로 설정
연결 시키고자 하는 두 값의 부모(집합)이 같은 경우 아직 연결 시키지 않았는데도 같은 부모(집합)에 속해 있기 때문에 이 두개를 연결 시키면 사이클이 발생
public void setChildToParent(int parent, int child) {
if (parent == child) {
return;
}
int parentParent = findParent(parent);
int childParent = findParent(child);
if (parentParent != childParent) {
this.parentArray.put(child, parentParent);
} else {
this.hasCycle = true;
}
}찾고자 하는 두 노드의 부모가 같다면 같은 부모(집합)에 속함을 표시
private boolean isConnected(int a, int b) {
return findParent(a) == findParent(b);
}사이클이 존재하는 여부 판별
public boolean hasCycle() {
return this.hasCycle;
}배열로 구현
정점의 수 만큼 본인의 부모(집합)을 본인으로 초기화
아직 정점들에 대한 정보에 대해 모르기 때문에 본인 스스로를 본인의 부모(집합)으로 설정
public class UnionFind {
private final int[] UNIONARR;
public UnionFind (int vertexNumber) {
UNIONARR = new int[vertexNumber+1];
for(int i = 0; i < UNIONARR.length; i++) {
UNIONARR[i] = i;
}
}
}노드들의 정보가 들어왔을때 노드의 부모 찾기
private int find (int vertex) {
if(UNIONARR[vertex] == vertex) {
return UNIONARR[vertex];
}
return UNIONARR[vertex] = find(UNIONARR[vertex]);
}재귀를 통해 본인 스스로가 부모(집합)인 경우까지 찾아 올라감
위의 find를 통해 부모를 찾고 다른 부모(집합)일 경우 child의 부모를 parent로 설정
public void union (int a, int b) {
int fa = find(a);
int fb = find(b);
if(fa != fb) UNIONARR[b] = UNIONARR[a];
}찾고자 하는 두 노드의 부모가 같다면 같은 부모(집합)에 속함을 표시
public boolean isConnected(int a, int b) {
return UNIONARR[a] == UNIONARR[b];
}최종 코드
HashMap
package Structure.Algorithme;
import java.util.Arrays;
import java.util.HashMap;
public class FindCommonParent {
private final HashMap<Integer ,Integer> parentArray;
private boolean hasCycle;
public FindCommonParent(int vertexNumber) {
this.parentArray = new HashMap<>();
this.hasCycle = false;
for(int i = 1; i <= vertexNumber; i++) {
this.parentArray.put(i,i);
}
}
private int findParent(int child) {
int parent = child;
while (this.parentArray.get(parent) != parent) {
parent = this.parentArray.get(parent);
}
return parent;
}
public void setChildToParent(int parent, int child) {
if (parent == child) {
return;
}
int parentParent = findParent(parent);
int childParent = findParent(child);
if (parentParent != childParent) {
this.parentArray.put(child, parentParent);
} else {
this.hasCycle = true;
//부모가될 노드와 자식 노드의 집합(부모)이 같다면 이미 같은 집합내에서 연결점이 있다는 뜻인데 여기서 서로 연결시키면 사이클이 발생
}
}
private boolean isConnected(int a, int b) {
return findParent(a) == findParent(b);
}
public void printArray() {
for(Integer key : this.parentArray.keySet()) {
System.out.printf("%d의 최종 부모는 %d\n",key, this.parentArray.get(key));
}
}
public boolean hasCycle() {
return this.hasCycle;
}
}배열
package Structure.Algorithme;
import java.util.Arrays;
public class UnionFind {
private final int[] UNIONARR;
public UnionFind (int vertexNumber) {
UNIONARR = new int[vertexNumber+1];
for(int i = 0; i < UNIONARR.length; i++) {
UNIONARR[i] = i;
}
}
private int find (int vertex) { //해당 정점의 최고 부모 노드를 찾아서 리턴함
if(UNIONARR[vertex] == vertex) {
return UNIONARR[vertex];
}
return UNIONARR[vertex] = find(UNIONARR[vertex]);
}
public void union (int a, int b) {
int fa = find(a);
int fb = find(b);
if(fa != fb) UNIONARR[b] = UNIONARR[a];
}
public boolean isConnected(int a, int b) {
return UNIONARR[a] == UNIONARR[b];
}
public void printArr () {
System.out.println(Arrays.toString(UNIONARR));
}
}깃허브
깃허브
정점의 수가 주어졌을때 그 정점들이 차레대로 배열에 빈 곳이 없게 다 채워진다면 배열의 풀이도 나쁘지 않겠지만 그렇지 않을 경우 HashMap은 존재하는 정점들만 다루기 때문에 HashMap이 더 유리한 것 같다.
