무방향 그래프에서 사이클 감지하기: DFS 알고리즘 완벽 가이드

개요

무방향 그래프(undirected graph)에 사이클(cycle)이 존재하는지 판별하는 가장 대표적인 방법은 DFS(깊이 우선 탐색)을 활용하는 것입니다. 핵심 원리는 다음과 같습니다.

탐색 도중 어떤 정점 v를 방문했을 때, 그와 인접한 정점 u가 이미 방문된 상태이면서 동시에 u가 v의 부모 정점이 아니라면, 그래프에는 사이클이 존재한다고 판단할 수 있습니다.

이 글에서는 두 정점 사이에 평행 간선(parallel edge, 중복 간선)이 존재하지 않는다고 가정합니다.

다음은 인접 행렬(adjacency matrix)로 표현된 그래프와 실행 결과 예시입니다.

입력 및 출력:
인접 행렬

    0 1 0 0 0
    1 0 1 1 0
    0 1 0 0 1
    0 1 0 0 1
    0 0 1 1 0

출력:
The graph has cycle.

알고리즘

사이클 감지 로직은 크게 두 부분으로 구성됩니다. 하나는 실제 탐색을 수행하는 DFS 재귀 함수이고, 다른 하나는 그래프의 모든 정점을 순회하며 사이클 여부를 확인하는 함수입니다.

dfs(vertex, visited, parent)

입력: 시작 정점, 방문 집합(visited), 해당 정점의 부모 노드
출력: 사이클을 발견하면 true, 아니면 false

dfs 시작
    현재 vertex를 방문 집합에 추가
    vertex와 인접한 모든 정점 v에 대해 반복:
        만약 v가 parent라면 → 건너뛰고 다음 정점 검사
        만약 v가 이미 방문 집합에 있다면 → true 반환 (사이클 발견)
        만약 dfs(v, visited, vertex)가 true라면 → true 반환
    반복 종료 후 false 반환
dfs 끝

hasCycle(graph)

입력: 주어진 그래프
출력: 사이클이 발견되면 true

hasCycle 시작
    그래프의 모든 정점 v에 대해 반복:
        만약 v가 이미 방문 집합에 있다면 → 다음 정점으로 넘어감
        만약 dfs(v, visited, φ)가 true라면 → true 반환  // 시작 정점의 부모는 null
    반복 종료 후 false 반환
hasCycle 끝

C++ 구현 예제

위 알고리즘을 C++ 코드로 구현하면 다음과 같습니다.

#include<iostream>
#include<set>
#define NODE 5
using namespace std;

int graph[NODE][NODE] = {
    {0, 1, 0, 0, 0},
    {1, 0, 1, 1, 0},
    {0, 1, 0, 0, 1},
    {0, 1, 0, 0, 1},
    {0, 0, 1, 1, 0}
};

bool dfs(int vertex, set<int>&visited, int parent) {
    visited.insert(vertex);
    for(int v = 0; v<NODE; v++) {
        if(graph[vertex][v]) {
            if(v == parent)     //v가 부모라면 그 방향으로는 진행하지 않음
                continue;
            if(visited.find(v) != visited.end())     //v가 이미 방문된 경우
                return true;
            if(dfs(v, visited, vertex))
                return true;
        }
    }
    return false;
}

bool hasCycle() {
    set<int> visited;       //방문 집합
    for(int v = 0; v<NODE; v++) {
        if(visited.find(v) != visited.end())     //v가 이미 방문된 경우 다음 반복으로
            continue;
        if(dfs(v, visited, -1)) {     //-1은 시작 정점에 부모가 없음을 의미
            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.

이처럼 DFS 탐색 과정에서 부모가 아닌 경로를 통해 이미 방문한 정점을 다시 만나게 되면 사이클이 존재하는 것으로 판단합니다. 위 구현은 인접 행렬을 사용하므로 시간 복잡도는 O(V²)이며, 인접 리스트를 사용하면 O(V + E)로 최적화할 수 있습니다. 연결 요소가 여러 개로 나뉜 그래프에서도 hasCycle 함수가 모든 정점을 순회하므로 어느 위치의 사이클이든 놓치지 않고 감지할 수 있습니다.