disjoint set 검색 결과
1 개의 검색 결과가 있습니다.
Algorithm

알고리즘 :: Union Find(Disjoint-Set) 알고리즘, 합 집합 찾기 알고리즘 (C/C++ /JAVA 구현)

Union Find 알고리즘 Union Find 알고리즘은 다른말로 Disjoint-Set(서로소 집합)알고리즘 이라고 하기도 한다. 다수의 노드들 중에 연결된 노드를 찾거나 노드들을 합칠때 사용하는 알고리즘이다. 1부터 10까지 노드들이 존재한다. 노드들은 서로 연결이 되어 있는데, 크게 3집단으로 나눠져있다. 1-2-3-4 5-6-7-8 9-10 초기 노드들간에 연결이 되기 전... 윗칸은 노드 번호 아랫칸은 부모 노드를 뜻한다. (위와 같은 형태 때문에, Union Find를 구현할때 보통 배열을 이용한다.) 연결정보를 갱신한다. 갱신을 할때 작은값을 기준으로 갱신한다. 예를들어, 1과 2가 연결이 되어있으면, '노드 2'의 값을 1로 바꾼다. 1-2-3-4는 모두 연결이 되어 있어, 같은 집단에 ..

2018. 4. 30. 23:34