13.2.2 분리 집합: 사이클이 형성되는지 어떻게 확인하지?

사이클이 생성되는지 확인할 때 가장 먼저 떠오르는 것이 DFS를 이용하는 방법입니다. V(G')=V(G)고 E(G')=ø인 그래프를 생성하고 최소 비용 신장 트리 T에 에지를 하나씩 추가할 때마다 그래프 G'에도 에지를 추가합니다. 이때 추가하기 전에 추가할 에지 e=(u, v)에서 u를 시작 정점으로 그래프 G'에 대해 DFS를 했을 때 visited[v]=TRUE라면 이미 경로가 있는 상태이므로 여기에 e=(u, v)를 삽입하면 그래프가 생깁니다. 그러므로 visited[v]=FALSE일 때만 에지 e=(u, v)를 삽입하면 되지요. 그런데 이렇게 하면 모든 에지에 대해 DFS를 해야 할지도 모릅니다. 이는 효율적이지 않지요. 이를 해결할 수 있는 자료 구조가 바로 분리 집합(disjoint set)입니다.

분리 집합은 내부적으로는 배열을 사용하며, 트리를 이용해서 분리되어 있는 집합을 표현합니다. 또 두 가지 중요한 연산을 지원합니다. FIND와 UNION 연산입니다. 그림으로 살펴보겠습니다(그림 13-12).

▲ 그림 13-12 분리 집합 1