집합으로 묶는 방식
A와 B가 연결되고 B와 C도 연결되었다면 세 원소를 같은 집합으로 관리할 수 있다. 서로 같은 대표에 연결되는지를 통해 같은 집합인지 확인한다. 대표는 자료구조가 선택한 표식이며 반드시 의미상 중심이거나 가장 작은 원소일 필요는 없다. 대표의 이름과 집합의 의미를 구분해야 한다.
간선 추가의 사례
처음에는 A, B, C가 각각 별개라고 하자. A와 B를 합치고 B와 C를 합치면 A와 C도 같은 집합이 된다. 이어 A와 C 사이에 간선을 더할 때는 이미 같은 집합인지 확인해 기존 연결을 알 수 있다. 이 아이디어는 무방향 그래프에서 간선을 추가하며 순환을 판정하는 구성에도 활용할 수 있다.
경로 압축의 의미
대표를 찾는 과정에서 중간 원소가 대표를 더 직접 가리키도록 바꾸면 뒤의 조회가 짧아질 수 있다. 집합을 합칠 때의 균형 규칙도 연산 비용에 영향을 준다. 부모 연결은 내부 관리용 구조이므로 원래 그래프의 실제 간선 경로와 같다고 보장되지 않는다. 대표까지의 내부 경로를 실제 이동 경로로 사용하면 안 된다.
삭제가 필요한 문제
기본 유니온 파인드는 합쳐진 집합을 일반적인 간선 삭제에 맞춰 다시 나누는 기능을 자동으로 제공하지 않는다. 연결을 끊었을 때도 다른 경로가 남는지 판단하려면 추가 자료나 다른 알고리즘이 필요할 수 있다. 모든 동적 그래프 문제에 같은 구조를 적용하기 전에 갱신 종류를 확인한다.
방향과 거리의 한계
같은 집합이라는 정보만으로 어떤 방향으로 이동 가능한지나 최단 거리가 얼마인지는 알 수 없다. 방향 그래프의 강한 연결성처럼 다른 관계를 다룰 때도 정의가 달라진다. 요구하는 질문이 단순한 무방향 연결 여부인지 먼저 판단한다. 연결성 외의 정보를 원하면 그 목적에 필요한 구조를 함께 유지해야 한다.