[그래프 이론] 서로소 집합 자료구조/ /서로소 집합을 활용한 사이클 판별

2021.07.30 - [자료구조 알고리즘] - [알고리즘] 그래프 이론/ 서로소 집합/ 서로소 집합 자료구조/

[알고리즘] 그래프 이론/ 서로소 집합/ 서로소 집합 자료구조/

 

 

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

서로소 집합은 다양한 알고리즘에 사용될 수 있는데, 특히 무방향 그래프 내에서의 사이클을 판별할 때 사용할 수 있다.

 

 

사이클 (정리중)

 

예제

{1, 2, 3}

union 1, 2

union 1, 3

union 2, 3

 

step 0  (초기 단계)

초기 단계에서는 모든 노드에 대하여 자기 자신을 부모로 부모 테이블을 초기화한다.

 

 

노드 번호	1	2	3
부모	1	2	3

 

 

step 1 (union 1, 2)

간선 (1, 2)를 확인한다.

노드 1의 루트 노드를 찾는다. → 1

노드 2의 루트 노드를 찾는다. → 2

루트 노드가 다르다 = 사이클이 발생하지 않았다. → 1과 2의 합집합(union)을 수행한다.

노드 1과 노드 2의 루트 노드는 1과 2이기 때문에 더 큰 번호에 해당하는 루트 노드 2를 자식 노드로 설정하고, 더 작은 번호에 해당하는 루트 노드 1을 부모 노드로 설정한다.

 

 

노드 번호	1	2	3
부모	1	1	3

 

 

step 2 (union 1, 3)

간선 (1, 3)을 확인한다.

노드 1의 루트 노드를 찾는다. → 1

노드 3의 루트 노드를 찾는다. → 3

루트 노드가 다르다 → 사이클이 발생하지 않았다. → 1과 3의 합집합(union)을 수행한다.

노드 1과 노드 3의 루트 노드는 1과 3이기 때문에 더 큰 번호에 해당하는 루트 노드 3을 자식 노드로 설정하고, 더 작은 번호에 해당하는 루트 노드 1을 부모 노드로 설정한다.

 

노드 번호	1	2	3
부모	1	1	1

 

 

step 3 (union 2, 3)

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

노드 2의 루트 노드를 찾는다. → 1

노드 3의 루트 노드를 찾는다. → 1

루트 노드가 같다 → 사이클이 발생하였다.

 

모든 union 연산 처리 완료

 

---

즉, 간선을 확인하는 것만으로 사이클을 판별할 수 있다.

 

이러한 사이클 판별 알고리즘은 그래프에 포함되어 있는 간선의 개수가 E개일 때 모든 간선을 하나씩 확인하며, 매 간선에 대하여 union 및 find 함수를 호출하는 방식으로 동작한다.

이 알고리즘은 간선에 방향성이 없는 무향 그래프에서만 적용 가능하다.

 

---

소스코드

def find_parent(parent, x):
    print('find_parent(',parent[x],',',x,')')
    # 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출
    if parent[x] != x:
        parent[x] = find_parent(parent, parent[x])
    return parent[x]


def union_parent(parent, a, b):
    print('union_parent(', a, ',', b, ')')
    a = find_parent(parent, a)
    b = find_parent(parent, b)
    if a < b:
        parent[b] = a
        print('parent 테이블', parent)
    else:
        parent[a] = b
        print('parent 테이블', parent)


v, e = map(int, input().split())
parent = [0] * (v + 1)  # 부모 테이블 초기화

print('parent 테이블', parent)

# 부모 테이블 상에서, 부모를 자기 자신으로 초기화
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):
        print('parent 테이블', parent)
        cycle = True
        break
    # 사이클이 발생하지 않았다면 합집합 수행
    else:
        print('parent 테이블', parent, end='\n\n')
        print('사이클이 발생하지 않았기때문에 a=', a, '와 b=', b, '의 합집합 수행')
        union_parent(parent, a, b)

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