[알고리즘] 사이클 탐지 (Cycle Detection)

100·2025년 3월 28일

자료구조 & 알고리즘

목록 보기

12/20

🔁 사이클 탐지 (Cycle Detection) - DFS / 위상 정렬 / 유니온 파인드 완전 정리

✅ 사이클이란?

그래프에서 사이클이란, 시작 정점으로 다시 돌아오는 경로가 존재하는 경우를 의미한다.
즉, 한 정점에서 출발해 연결된 간선을 따라가다 보면 자기 자신을 다시 만나게 되는 경우다.

✅ 사이클이 중요한 이유

트리는 사이클이 없는 연결 그래프이다
MST는 사이클 없이 모든 정점을 연결하는 최소 구조
위상 정렬은 사이클이 없는 방향 그래프(DAG)에서만 가능
유효한 연결 그래프인지 판단할 때 자주 사용됨

✅ 사이클 탐지 방법 요약

방법	사용 그래프	핵심 아이디어
DFS (무방향)	무방향 그래프	부모 노드 제외하고 방문한 노드 발견 시 사이클
유니온 파인드	무방향 그래프	두 정점이 같은 집합에 있으면 사이클
DFS (방향)	방향 그래프	방문 중인 노드를 다시 방문하면 사이클
위상 정렬	방향 그래프	모든 정점을 정렬하지 못하면 사이클 존재

✅ 무방향 그래프에서의 사이클 탐지

🔸 DFS 방식

def has_cycle_dfs(graph, v, visited, parent):
    visited[v] = True
    for neighbor in graph[v]:
        if not visited[neighbor]:
            if has_cycle_dfs(graph, neighbor, visited, v):
                return True
        elif neighbor != parent:
            return True
    return False

# 예시
graph = {
    0: [1],
    1: [0, 2],
    2: [1, 3],
    3: [2, 0]  # 사이클 존재
}

visited = [False] * len(graph)
has_cycle = False
for v in range(len(graph)):
    if not visited[v]:
        if has_cycle_dfs(graph, v, visited, -1):
            has_cycle = True
            break

print("사이클 존재 여부:", has_cycle)

🔸 유니온 파인드 방식

def find(parent, x):
    if parent[x] != x:
        parent[x] = find(parent, parent[x])
    return parent[x]

def union(parent, a, b):
    a_root = find(parent, a)
    b_root = find(parent, b)
    if a_root == b_root:
        return False  # 사이클 발생
    parent[b_root] = a_root
    return True

edges = [(0, 1), (1, 2), (2, 3), (3, 0)]  # 사이클 존재
n = 4
parent = list(range(n))

cycle = False
for a, b in edges:
    if not union(parent, a, b):
        cycle = True
        break

print("사이클 존재 여부:", cycle)

✅ 방향 그래프에서의 사이클 탐지

🔸 DFS 방문 상태 추적 방식

def has_cycle_dfs_directed(graph):
    n = len(graph)
    visited = [0] * n  # 0: 미방문, 1: 방문 중, 2: 방문 완료

    def dfs(v):
        visited[v] = 1
        for neighbor in graph[v]:
            if visited[neighbor] == 1:
                return True
            if visited[neighbor] == 0:
                if dfs(neighbor):
                    return True
        visited[v] = 2
        return False

    for i in range(n):
        if visited[i] == 0:
            if dfs(i):
                return True
    return False

🔸 위상 정렬 기반 방식 (진입차수 활용)

from collections import deque

def has_cycle_topo(graph):
    n = len(graph)
    indegree = [0] * n
    for u in graph:
        for v in graph[u]:
            indegree[v] += 1

    q = deque([i for i in range(n) if indegree[i] == 0])
    count = 0

    while q:
        node = q.popleft()
        count += 1
        for neighbor in graph[node]:
            indegree[neighbor] -= 1
            if indegree[neighbor] == 0:
                q.append(neighbor)

    return count != n  # 정점 수만큼 처리 못했으면 사이클 존재

✅ 사이클 탐지 방식 비교

방식	사용 그래프	구현 난이도	사이클 경로 추적	장점	단점
DFS + 부모 추적	무방향	중	가능	구조 직관적	방향 그래프엔 부적절
유니온 파인드	무방향	하	불가	빠르고 단순	방향 그래프엔 사용 불가
DFS 상태 추적	방향	중	가능	직접 흐름 추적 가능	상태값 관리 필요
위상 정렬 방식	방향	하	불가	구현 쉬움, 실전 선호	경로 추적 불가