Union find(합집합 찾기, 서로소 집합) 알고리즘

Union find 알고리즘은 여러개의 공통점이 없는 노드들이 존재할 때, 그 중 선택한 두개의 노드가 서로 같은 그래프에 속하는지 판별하는 알고리즘이다. 노드 번호 1 2 3 4 5 6 7 부모 노드 번호 1 2 3 4 5 6 7 현재는 각 노드들이 부모 노드번호로 자기 자신을 가지고 있는, 각자 자기 자신만을 집합으로 가지고 있는 상태이다. 부모 노드 번호는 자신이 어떤 부모에 포함되어 있는지를 나타낸다. 노드 번호 1 2 3 4 5 6 7 부모 노드 번호 1 2 3 3 5 6 7 만약 노드 3, 4가 연결되었다면 둘 중 더 작은 값(여기서는 1)로 부모 노드를 합친다. 이것을 합침(Union)이라고 한다. 만약 4, 5도 연결되었다면 테이블은 아래와 같을 것이다. 노드 번호 1 2 3 4 5 6 7..

2022.05.24