깊이 우선 탐색(Depth First Search, DFS) 알고리즘을 사용하면 유향 그래프(directed graph)에서 사이클(cycle)을 효과적으로 감지할 수 있습니다. 어떤 노드가 자기 자신을 가리키는 셀프 루프(self-loop)를 가지고 있다면 이는 곧바로 사이클로 간주되며, 자식 노드에서 부모 노드로 되돌아가는 간선이 존재하는 경우 역시 사이클로 판단합니다.
간선으로 연결되지 않은 비연결 그래프(disconnected graph)의 경우 여러 개의 독립적인 트리가 존재할 수 있는데, 이러한 구조를 포레스트(forest)라고 부릅니다. 이때는 포레스트를 구성하는 모든 트리에 대해 각각 사이클 검사를 수행해야 합니다.
흰색·회색·검은색 세 가지 집합
이 접근 방식에서는 DFS 순회 과정에서 각 노드의 상태를 추적하기 위해 서로 다른 세 개의 집합(set)을 사용합니다. 초기에는 모든 노드가 흰색(White) 집합에 저장됩니다. 새로운 노드를 방문하는 순간 해당 노드는 흰색 집합에서 제거되고 회색(Grey) 집합으로 옮겨지며, 백트래킹(backtracking)이 완료되어 그 노드에 대한 탐색 작업이 모두 끝나면 회색 집합에서 검은색(Black) 집합으로 이동합니다.
- 흰색(White): 아직 한 번도 방문되지 않은 노드
- 회색(Grey): 현재 DFS 탐색 경로상에 있는, 즉 방문이 진행 중인 노드
- 검은색(Black): 해당 노드와 연결된 모든 탐색이 완료된 노드
핵심 아이디어는 간단합니다. DFS 도중 어떤 노드의 이웃을 살펴보았을 때 그 이웃이 회색 집합에 속해 있다면, 이는 현재 진행 중인 탐색 경로로 되돌아가는 간선(백 엣지, back edge)이 존재한다는 뜻이며, 따라서 그래프에 사이클이 있다는 것을 의미합니다.
입력과 출력
입력:
인접 행렬(Adjacency Matrix)
0 1 0 0 0
0 0 0 0 0
1 0 0 1 0
0 0 0 0 1
0 0 1 0 0
출력:
그래프에 사이클이 존재합니다.
알고리즘
dfs(curr, wSet, gSet, bSet)
입력: 현재 노드(curr), 흰색 집합, 회색 집합, 검은색 집합
출력: 사이클이 존재하면 true, 아니면 false
시작
curr를 흰색 집합에서 삭제하고 회색 집합에 추가한다
그래프에서 curr와 연결된 모든 노드 v에 대해 반복:
만약 v가 검은색 집합에 있다면
건너뛰고 다음 반복으로 진행한다
만약 v가 회색 집합에 있다면
true를 반환한다 (사이클 발견)
만약 dfs(v, wSet, gSet, bSet)의 결과가 true라면
true를 반환한다
반복 종료
curr를 회색 집합에서 삭제하고 검은색 집합에 추가한다
false를 반환한다
종료
hasCycle(graph)
입력: 주어진 그래프
출력: 그래프에 사이클이 존재하면 true
시작
처음에 모든 노드를 흰색 집합에 삽입한다
흰색 집합에 요소가 남아 있는 동안 반복:
그래프의 모든 노드 v에 대해:
만약 v가 흰색 집합에 있다면
dfs(v, wSet, gSet, bSet)의 결과가 true이면
true를 반환한다
반복 종료
반복 종료
false를 반환한다
종료
C++ 구현 예제
#include<iostream>
#include<set>
#define NODE 5
using namespace std;
int graph[NODE][NODE] = {
{0, 1, 0, 0, 0},
{0, 0, 0, 0, 0},
{1, 0, 0, 1, 0},
{0, 0, 0, 0, 1},
{0, 0, 1, 0, 0}
};
bool dfs(int curr, set<int>&wSet, set<int>&gSet, set<int>&bSet) {
//현재 노드를 흰색 집합에서 회색 집합으로 이동
wSet.erase(wSet.find(curr));
gSet.insert(curr);
for(int v = 0; v < NODE; v++) {
if(graph[curr][v] != 0) { //모든 인접 정점에 대해
if(bSet.find(v) != bSet.end())
continue; //정점이 검은색 집합에 있는 경우 무시
if(gSet.find(v) != gSet.end())
return true; //회색 집합에 있으면 사이클
if(dfs(v, wSet, gSet, bSet))
return true; //사이클 발견
}
}
//현재 노드를 회색 집합에서 검은색 집합으로 이동
gSet.erase(gSet.find(curr));
bSet.insert(curr);
return false;
}
bool hasCycle() {
set<int> wSet, gSet, bSet; //흰색, 회색, 검은색 세 개의 집합
for(int i = 0; i<NODE; i++)
wSet.insert(i); //처음에 모든 노드를 흰색 집합에 추가
while(wSet.size() > 0) {
for(int current = 0; current < NODE; current++) {
if(wSet.find(current) != wSet.end())
if(dfs(current, wSet, gSet, bSet))
return true;
}
}
return false;
}
int main() {
bool res;
res = hasCycle();
if(res)
cout << "The graph has cycle." << endl;
else
cout << "The graph has no cycle." << endl;
}
실행 결과
The graph has cycle.
시간 복잡도
이 알고리즘은 각 정점과 간선을 최대 한 번씩만 방문하므로, 정점의 수를 V, 간선의 수를 E라고 할 때 시간 복잡도는 O(V + E)입니다. 공간 복잡도 역시 세 개의 집합과 재귀 호출 스택을 위해 O(V)의 공간이 필요합니다.