[Python] 서로소 집합을 활용하여 그래프 사이클 확인하기 (Graph Cycle)

직전에 알아봤던 서로소 집합 알고리즘은 다양한 알고리즘에서 활용될 수 있다.

특히, 서로소 집합은 무방향 그래프 내에서의 사이클을 판별할 때 사용할 수 있다는 특징이 있다. 참고로 방향 그래프에서의 사이클 여부는 DFS로 판별할 수 있다.

 

서로소 집합의 연산은 find와 union으로 두가지가 있으며, 여기서 union은 그래프의 간선정보로 이해할 수 있다고 했다.

따라서, 간선을 하나씩 확인하면서 두 노드가 포함되어 있는 집합을 합치는 과정을 반복하는 것만으로도 사이클을 판별할 수 있다.

 

알고리즘의 순서는 아래와 같다.

 

서로소 집합을 활용한 사이클 판별 알고리즘

1. 각 간선을 활인하며 두 노드의 루트 노드를 확인한다.
   1. 루트 노드가 서로 다르다면, 두 노드에 대해서 union연산을 수행한다.
   2. 루트 노드가 서로 같다면, Cycle이 발생한 것이다.
2. 그래프에 포함되어 있는 모든 간선에 대하여 1번 과정을 반복한다.

 

그림으로 도식화하여 이를 다시 확인해보자.

 

1. 초기상태

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

 

2. 간선 (1, 2) 확인

 

가장 먼저 간선 (1, 2)를 확인한다. 노드 1과 노드 2의 루트 노드는 각각 1과 2이다. 따라서 두 노드의 루트 노드를 더욱 작은 값인 1로 업데이트 해준다.

 

3. 간선 (1, 3) 확인

이어서 간선 (1, 3)을 확인한다. 노드 1과 노드 3의 루트 노드는 각각 1과 3이되며, 위와 같은 방식으로 3의 루트 노드를 1로 변환해준다.

 

4. 간선 (2, 3) 확인

이후에, 간선 (2, 3)을 확인하는데, 이미 부모노드가 같기 때문에, 사이클이 발생했다고 판단할 수 있게 된다.

 

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

 

앞에서 설명했지만, 반드시 무방향 그래프(uni-directed graph)에서만 적용할 수 있다.

 

사이클 판별 알고리즘 코드

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

# 간선 정보 입력 받기
v, e = map(int, input().split())
parent = [i for i in range(v+1)]

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
    else:
        union_parent(parent, a, b)

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

 

알고리즘은 기존 서로소 집합 알고리즘과 크게 다르지 않다. main함수 부분에서 find를 통해 두 간선의 부모노드를 보고 같은 집합에 속해있는지 확인해주는 것으로 사이클을 판별한다.

 

앞선 예시 입력문을 넣어보면 아래와 같은 결과가 출력된다.

 

- 입력

3 3
1 2
1 3
2 3

 

- 출력

사이클이 발생하였습니다.