[그래프] - 서로소 집합과 사이클 판별

서로소 집합 자료 구조 : 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조

 

서로소 집합 자료구조는 union과 find 2개의 연산으로 조작한다.

 

union연산 : 2개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산

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

 

트리를 이용한 서로소 집합 계산 알고리즘

1. union 연산을 확인하여 두 노드 A,B를 확인한다.

   1) A와 B의 루트 노드 A', B'을 각각 찾는다.

   2) A'를 B'의 부모 노드로 설정한다( B'이 A'을 가리키도록 한다.)

2. 모든 Union 연산을 처리할 때 까지 1번 과정을 반복한다.

 

A'와B' 중 에서 더 번호가 작은 원소가 부모노드가 되도록 구현

 

A'가 1이고 B'가 3이라면 B'가 A'를 가리키도록 설정한다.

'가리킨다'는 표현은 부모 노드로 설정한다는 의미이다.

 EX) B'가 A'를 부모 노드로 설정하는 것을 그래프로 시각화할 때 B'와 A'를 간선으로 연결하는 형태로 그래프

 

 

전체 집합 {1, 2, 3, 4, 5, 6}이 있을 때 아래와 같은 union 연산이 있다고 가정.

 

STEP 0 먼저 노드의 개수(V) 크기의 부모 테이블을 초기화 한다.

이때 모든 원소가 자기 자신을 부모로 가지도록 설정한다.

부모 테이블은 특정 노드의 부모에 대한 정보만 담고 있다.

그래서 실제 해당 노드의 루트 노드를 확인하기 위해서는 재귀적으로 부모를 거슬러 올라가서 확인한다.

 

 

STEP 1 union 1,4

첫 번째 연산을에서 1,4를 합치기 위해 노드 1과 노드4의 루트 노드를 각각 찾으면 된다.

현재 루트 노드는 각각 1과4이기 때문에 더 큰 번호에 해당하는 루트노드 4의 부모를 1로 설정한다.

 

STEP 2 union 2,3

이번에는 노드2와 노드3의 루트노드를 각각 찾으면 된다.

현재 루트 노드는 각각 2 와 3이기 때문에 더 큰 번호에 해당하는 루트 노드 3의 부모를 2로 설정한다.

STEP 3 union 2,4

현재 루트 노드는 각각 2와 1이기 때문에 더 큰 번호에 해당하는 루트 노드 2의 부모를 1로 설정한다.

 

 

STEP 4 union 5,6

현재 루트 노드는 각각 5와 6이기 때문에 더 큰 번호에 해당하는 루트노드 6의 부모를 5로 설정한다.

 

여기 까지 union연산에 대해 모두 처리 했다.

union연산을 위해서는 부모테이블을 항상 가지고 있어야 한다.

또한 루트 노드를 즉시 계산할 수 없고, 부모테이블을 계속 확인하며 재귀적으로 거슬러 올라가야한다.

EX) STEP4에서 노드 3의 부모 노드는 2라고 설정되어 있지만 노드2의 부모노드는 1이기 때문에 최종적으로 노드 3의 루트 노드는 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

# 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=' ')

 

 

 

 

 

 

 

 

서로소 집합을 이용한 사이클 판별

서로소 집합은 무방향 그래프 내에서 사이클을 판별할 때 사용할 수 있다.

(방향 그래프의 사이클 여부는 DFS를 이용하여 판별가능 )

 

Union연산은 그래프에서의 간선으로 표현될 수 있다.

따라서 간선을 하나씩 확인하면서 두 노드가 포함되어 있는 집합을 합치는 과정을 반복하는 것을 통해 사이클을 판별할 수있다. 알고리즘은 아래와 같다.

 

1. 각 간선을 확인하며 두 노드의 루트 노드를 확인하다.

       1) 루트 노드가 서로 다르다면 두 노드에 대하여 union연산을 수행한다

       2) 루트 노드가 서로 같다면 사이클(Cycle)이 발생한 것이다.

2. 그래프에 포함되어 있는 모든 간선에 대하여 1번 과정을 반복한다.

 

그래프의 사이클을 판별하는과정

 

STEP 0 모든 노드에 대하여 자기 자신을 부모로 설정한느 형래로 부모테이블을 초기화

 

STEP 1 간선 (1,2)를 확인해 보자.

노드 1과 노드 2의 루트 노드는 각각 1과 2이다.

따라서 더 큰 번호를 갖는 노드 2의 부모 노드를 1로 변경한다.

 

 

STEP 2 이어서 간선 (1,3)을 확인한다.

노드 1과 노드 3의 루트 노드는 각각 1과 3이다.

따라서 더큰 번호를 갖는 노드 3의 부모 노드를 1로 변경한다.

 

STEP 3 이후 (2,3) 간선을 확인한다.

다만, 이때 노드 2와 노드 3이 이미 루트 노드로 노드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("사이클이 발생하지 않았습니다.")