그래프 Cycle Detection: DFS, Union-Find와 Kahn

Cycle Detection은 현재 탐색 경로에 이미 포함된 정점으로 다시 돌아갈 수 있는지 확인하는 문제입니다.

Dependency Graph, Workflow, Build System, DAG Validation에서 매우 중요합니다.

방향 그래프

보통 세 상태를 사용합니다.

0 = unvisited
1 = visiting
2 = finished

visiting 상태의 정점으로 가는 Edge는 Back Edge이며 Cycle을 의미합니다.

무방향 그래프

Parent를 추적해야 합니다.

방문한 이웃이 현재 정점의 Parent라면 Cycle이 아닙니다.

visited neighbor != parent
→ cycle

Kahn Algorithm

Topological Sort 과정에서 모든 정점을 처리하지 못하면 Directed Graph에 Cycle이 존재합니다.

Union-Find

Undirected Graph에서 새로운 Edge의 두 끝점이 이미 같은 Set에 있다면 그 Edge는 Cycle을 만듭니다.

실제 활용

• Circular Dependency
• Package Dependency
• Workflow Validation
• Course Prerequisite
• Build Graph
• Spreadsheet Circular Reference
• Service Dependency

Floyd

Floyd Cycle Detection은 일반 그래프보다는 Linked List나 Functional Graph에 적합합니다.

복잡도

DFS와 Kahn:

O(V + E)

정리

Directed Graph는 recursion state가 핵심이고, Undirected Graph는 Parent tracking 또는 Union-Find가 핵심입니다.