[그래프] 그래프 알고리즘 (1) 서로소 집합

서로소 집합

• 서로소 집합이란 공통 원소가 없는 두 집합 의미
  • ex) {1, 2}와 {3, 4}는 공통 원소가 없으므로 서로소 관계
  • ex) {1, 2}와 {2, 3}은 공통 원소가 있으므로 서로소 관계가 아님

서로소 집합 자료구조

• 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조
• union과 find 두 가지 연산으로 조작
  • union (합집합) 연산
    • 2개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산
  • find (찾기) 연산
    • 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산
• 트리 자료구조를 이용하여 집합 표현
• 트리를 이용한 서로소 집합 계산 알고리즘
  1. union 합집합 연산을 확인하여, 서로 연결된 두 노드 A, B를 확인한다
     1. A와 B의 루트 노드 A'과 B'을 각각 찾는다
     2. 둘 중 값이 더 작은 루트 노드를 다른 루트 노드의 부모 노드로 설정한다 (ex. A'이 B'보다 작다면 A'을 B'의 부모노드로 설정)
  2. 모든 union 연산을 처리할 때까지 1번 과정을 반복한다
• 서로소 집합 알고리즘 소스코드 (경로 압축 기법 적용)
  • 노드의 개수 (V) 크기의 부모 테이블 초기화
    • 모든 원소가 자기 자신을 부모로 가지도록 초기화
    • 부모 테이블은 특정한 노드의 부모에 대해서만 저장하고 있으며, 실제로 루트를 확인하기 위해서는 재귀적으로 부모를 거슬러 올라가 최종적인 루트 노드를 찾아야함
    • ex) 1 ⬅️ 2 ⬅️ 3 과 같은 관계라면, 3의 루트 노드를 찾기 위해서는 3 ➡️ 2  ➡️1 로 거슬러 올라가야 함
  • 경로 압축 기법
    • find_parent() 함수를 단순히 재귀적으로 구현하면 비효율적임
      • 최악의 경우 모든 노드를 다 확인하느라 시간복잡도가 O(V)
      • find 혹은 union 연산의 개수가 M일 때, 전체 시간 복잡도는 O(VM)
    • 경로 압축 기법으로 시간 복잡도 개선
      • find 함수를 재귀적으로 호출한 뒤에 부모 테이블값을 갱신하는 기법
      • 각 노드에 대하여 find 함수를 호출한 뒤, 해당 노드의 루트 노드가 바로 부모 노드가 됨
      • 루트 노드에 대해 더욱 빠르게 접근 가능

# 특정 원소가 속한 집합을 찾기
def find_parent(parent, x):
  # 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출
  if parent[x] != x:
    parent[x] = find_parent(parent, parent[x])
  return parent[x]

# 두 원소가 속한 집합을 합치기
def union_parent(parent, a, b):
  a = find_parent(parent, a)
  b = find_parent(parent, b)
  if a < b:
    parent[b] = a
  else:
    parent[a] = b

# 노드의 개수와 간선(union 연산)의 개수 입력받기
v, e = map(int, input().split())
parent = [0] * (v + 1) # 부모 테이블 초기화

# 부모 테이블 상에서 부모를 자기 자신으로 초기화
for i in range(1, v + 1):
  parent[i] = i

# union 연산을 각각 수행
for i in range(e):
  a, b = map(int, input().split())
  union_parent(parent, a, b)

# 각 원소가 속한 집합 출력
print('각 원소가 속한 집합: ', end = ' ')
for i in range(1, v + 1):
  print(find_parent(parent, i), end = ' ')

print()

# 부모 테이블 내용 출력
print('부모 테이블: ', end = ' ')
for i in range(1, v + 1):
  print(parent[i], end = ' ')

• 입력 예시

6 4 1 4 2 3 2 4 5 6

• 출력 예시

각 원소가 속한 집합:  1 1 1 1 5 5  부모 테이블:  1 1 1 1 5 5

• 경로 압축 방법을 적용한, 서로소 집합 알고리즘의 시간 복잡도는 O(V + M(1 + log(2-M/V)V)))

무향 그래프의 사이클 판별

• 서로소 집합을 이용하여 무방향 그래프 내에서의 사이클 판별 가능
  • 간선에 방향이 없는 무향 그래프에만 적용 가능
• 알고리즘
  1. 각 간선을 확인하며 두 노드의 루트 노드를 확인한다
     1. 루트 노드가 서로 다르다면 두 노드에 대하여 union 연산을 수행한다
     2. 루트 노드가 서로 같다면 사이클이 발생한 것이다 
  2. 그래프에 포함되어 있는 모든 간선에 대하여 1번 과정을 반복한다
• 소스코드

# 특정 원소가 속한 집합을 찾기
def find_parent(parent, x):
  # 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출
  if parent[x] != x:
    parent[x] = find_parent(parent, parent[x])
  return parent[x]

# 두 원소가 속한 집합을 합치기
def union_parent(parent, a, b):
  a = find_parent(parent, a)
  b = find_parent(parent, b)
  if a < b:
    parent[b] = a
  else:
    parent[a] = b

# 노드의 개수와 간선(union 연산)의 개수 입력받기
v, e = map(int, input().split())
parent = [0] * (v + 1) # 부모 테이블 초기화

# 부모 테이블 상에서 부모를 자기 자신으로 초기화
for i in range(1, v + 1):
  parent[i] = i

# 사이클 발생 여부
cycle = False

for i in range(e):
  a, b = map(int, input().split())
  # 사이클이 발생한 경우 종료
  if find_parent(parent, a) == find_parent(parent, b):
    cycle = True
    break
  # 사이클이 발생하지 않았다면 합집합(union) 수행
  else:
    union_parent(parent, a, b)

if cycle:
  print('사이클이 발생했습니다')
else:
  print('사이클이 발생하지 않았습니다')

• 입력 예시

3 3 1 2 1 3 2 3

• 출력 예시

사이클이 발생했습니다