무방향 그래프(undirected graph)에 사이클(cycle)이 존재하는지 확인해야 하는 경우, 파이썬에서는 collections 모듈의 deque를 이용해 너비 우선 탐색(BFS) 기반으로 이를 간단하게 구현할 수 있습니다. 핵심 아이디어는 정점을 탐색하는 도중 이미 방문한 인접 정점을 다시 만났을 때, 해당 정점이 현재 정점의 바로 이전 정점(부모)이 아니라면 사이클이 존재한다고 판단하는 것입니다.
또한 그래프가 하나의 연결 요소로만 이루어져 있다는 보장이 없기 때문에, 모든 정점을 순회하면서 아직 방문하지 않은 정점마다 사이클 검사를 수행하는 것이 안전합니다.
예제 코드
from collections import deque
def add_edge(adj: list, u, v):
adj[u].append(v)
adj[v].append(u)
def detect_cycle(adj: list, s, V, visited: list):
parent = [-1] * V
q = deque()
visited[s] = True
q.append(s)
while q:
u = q.pop()
for v in adj[u]:
if not visited[v]:
visited[v] = True
q.append(v)
parent[v] = u
elif parent[u] != v:
return True
return False
def cycle_disconnected(adj: list, V):
visited = [False] * V
for i in range(V):
if not visited[i] and detect_cycle(adj, i, V, visited):
return True
return False
if __name__ == '__main__':
V = 5
adj = [[] for _ in range(V)]
add_edge(adj, 0, 1)
add_edge(adj, 1, 2)
add_edge(adj, 2, 0)
add_edge(adj, 2, 3)
add_edge(adj, 2, 1)
print('그래프에는 5개의 정점이 있습니다')
print('0-->1')
print('1-->2')
print('2-->0')
print('2-->3')
print('2-->1')
if cycle_disconnected(adj, V):
print('사이클이 존재합니까?')
print('예')
else:
print('사이클이 존재합니까?')
print('아니요')
출력 결과
그래프에는 5개의 정점이 있습니다 0-->1 1-->2 2-->0 2-->3 2-->1 사이클이 존재합니까? 예
코드 설명
필요한 패키지인 collections.deque를 가져옵니다.
add_edge 함수는 무방향 그래프의 특성에 맞게 두 정점을 양방향으로 연결하는 간선을 인접 리스트에 추가합니다.
detect_cycle 함수는 시작 정점 s부터 탐색을 수행하며, 방문 배열과 부모 배열을 관리하면서 사이클 여부를 판별합니다.
cycle_disconnected 함수는 그래프가 여러 개의 연결 요소로 분리되어 있어도 놓치지 않도록 전체 정점을 순회하며 사이클 검사를 호출합니다.
add_edge 함수를 통해 그래프에 간선들을 추가합니다.
마지막으로 cycle_disconnected 함수를 호출한 뒤 그 결과를 콘솔에 출력합니다.
동작 원리
탐색 중 정점 u의 인접 정점 v를 살펴볼 때, v를 아직 방문하지 않았다면 방문 처리 후 큐에 삽입하고 부모 정보를 기록합니다. 반면 v가 이미 방문된 상태인데 v가 u의 부모가 아니라면, 동일한 정점 쌍을 잇는 또 다른 경로가 존재한다는 뜻이므로 사이클이 있다고 판단하고 즉시 True를 반환합니다.
이 알고리즘의 시간 복잡도는 O(V + E)이며, 방문 배열·부모 배열·큐 저장에 공간 복잡도 O(V)가 소요됩니다. 위 예제에서는 0→1→2→0으로 이어지는 경로 때문에 사이클이 존재한다는 결과가 출력됩니다.