DFS 심화 — 사이클 탐지, 위상 정렬, 강연결 요소

DFS는 단순히 깊이 우선으로 탐색하는 것이 아닙니다. DFS가 만들어내는 트리 구조에서 사이클 탐지, 위상 정렬, 강연결 요소까지 끌어낼 수 있습니다.

DFS 기본 복습

깊이 우선 탐색(Depth-First Search)은 한 방향으로 끝까지 탐색한 후, 되돌아와서 다른 방향을 탐색하는 알고리즘입니다.

JAVA

public static void dfs(List<List<Integer>> graph, int node, boolean[] visited) {
    visited[node] = true;
    System.out.print(node + " ");

    for (int next : graph.get(node)) {
        if (!visited[next]) {
            dfs(graph, next, visited);
        }
    }
}

DFS 트리와 간선 분류

DFS를 수행하면 그래프의 간선이 네 가지로 분류됩니다.

간선 유형	설명	사이클 관련
Tree Edge	DFS 트리를 구성하는 간선	X
Back Edge	조상 노드로 향하는 간선	사이클 존재
Forward Edge	자손 노드로 향하는 간선 (트리 경로 외)	X
Cross Edge	다른 서브트리의 노드로 향하는 간선	X

간선 분류 구현

JAVA

static int[] discoveryTime;
static int[] finishTime;
static int timer = 0;
static int[] color; // 0: 미방문, 1: 진행중, 2: 완료

public static void classifyEdges(List<List<Integer>> graph, int node) {
    color[node] = 1; // 진행중
    discoveryTime[node] = timer++;

    for (int next : graph.get(node)) {
        if (color[next] == 0) {
            // Tree Edge
            classifyEdges(graph, next);
        } else if (color[next] == 1) {
            // Back Edge — 사이클 발견!
            System.out.println("Back edge: " + node + " → " + next);
        } else if (discoveryTime[node] < discoveryTime[next]) {
            // Forward Edge
        } else {
            // Cross Edge
        }
    }

    color[node] = 2; // 완료
    finishTime[node] = timer++;
}

사이클 탐지

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

Back edge가 존재하면 사이클이 있습니다. 노드의 상태를 세 가지(미방문, 진행중, 완료)로 관리합니다.

JAVA

public static boolean hasCycle(List<List<Integer>> graph, int n) {
    int[] state = new int[n]; // 0: 미방문, 1: 진행중, 2: 완료

    for (int i = 0; i < n; i++) {
        if (state[i] == 0 && dfsCycle(graph, i, state)) {
            return true;
        }
    }
    return false;
}

private static boolean dfsCycle(List<List<Integer>> graph, int node, int[] state) {
    state[node] = 1; // 진행중

    for (int next : graph.get(node)) {
        if (state[next] == 1) return true;  // back edge → 사이클!
        if (state[next] == 0 && dfsCycle(graph, next, state)) return true;
    }

    state[node] = 2; // 완료
    return false;
}

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

무방향 그래프에서는 부모를 통해 돌아오는 것을 제외해야 합니다.

JAVA

public static boolean hasCycleUndirected(List<List<Integer>> graph, int n) {
    boolean[] visited = new boolean[n];

    for (int i = 0; i < n; i++) {
        if (!visited[i] && dfsCycleUndirected(graph, i, -1, visited)) {
            return true;
        }
    }
    return false;
}

private static boolean dfsCycleUndirected(List<List<Integer>> graph,
                                           int node, int parent, boolean[] visited) {
    visited[node] = true;

    for (int next : graph.get(node)) {
        if (!visited[next]) {
            if (dfsCycleUndirected(graph, next, node, visited)) return true;
        } else if (next != parent) {
            return true; // 부모가 아닌 이미 방문한 노드 → 사이클
        }
    }
    return false;
}

연결 요소 (Connected Components)

무방향 그래프의 연결 요소

JAVA

public static int countComponents(List<List<Integer>> graph, int n) {
    boolean[] visited = new boolean[n];
    int count = 0;

    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            dfs(graph, i, visited);
            count++;
        }
    }
    return count;
}

강연결 요소 (SCC) — Kosaraju 알고리즘

방향 그래프에서 ** 임의의 두 정점 사이에 양방향 경로가 존재하는** 최대 부분 그래프를 강연결 요소라 합니다.

JAVA

public static List<List<Integer>> kosaraju(List<List<Integer>> graph, int n) {
    // 1단계: 원래 그래프에서 DFS, 종료 시간 순서 기록
    boolean[] visited = new boolean[n];
    Deque<Integer> stack = new ArrayDeque<>();

    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            dfsOrder(graph, i, visited, stack);
        }
    }

    // 2단계: 역방향 그래프 생성
    List<List<Integer>> reversed = new ArrayList<>();
    for (int i = 0; i < n; i++) reversed.add(new ArrayList<>());
    for (int u = 0; u < n; u++) {
        for (int v : graph.get(u)) {
            reversed.get(v).add(u);
        }
    }

    // 3단계: 역방향 그래프에서 종료 시간 역순으로 DFS
    Arrays.fill(visited, false);
    List<List<Integer>> sccs = new ArrayList<>();

    while (!stack.isEmpty()) {
        int node = stack.pop();
        if (!visited[node]) {
            List<Integer> scc = new ArrayList<>();
            dfsSCC(reversed, node, visited, scc);
            sccs.add(scc);
        }
    }
    return sccs;
}

private static void dfsOrder(List<List<Integer>> graph, int node,
                              boolean[] visited, Deque<Integer> stack) {
    visited[node] = true;
    for (int next : graph.get(node)) {
        if (!visited[next]) dfsOrder(graph, next, visited, stack);
    }
    stack.push(node); // 종료 시간 순
}

private static void dfsSCC(List<List<Integer>> graph, int node,
                            boolean[] visited, List<Integer> scc) {
    visited[node] = true;
    scc.add(node);
    for (int next : graph.get(node)) {
        if (!visited[next]) dfsSCC(graph, next, visited, scc);
    }
}

Kosaraju 알고리즘의 핵심: ** 원래 그래프에서 종료 시간 역순으로 역방향 그래프를 DFS**하면 SCC가 분리됩니다.

절단점과 다리 (Articulation Point & Bridge)

무방향 그래프에서 제거하면 그래프가 분리되는 정점(절단점)이나 간선(다리)을 찾습니다. Tarjan의 알고리즘을 사용합니다.

JAVA

static int[] disc, low;
static boolean[] visited, isArticulation;
static int timer = 0;

public static void findArticulationPoints(List<List<Integer>> graph, int node, int parent) {
    visited[node] = true;
    disc[node] = low[node] = timer++;
    int children = 0;

    for (int next : graph.get(node)) {
        if (!visited[next]) {
            children++;
            findArticulationPoints(graph, next, node);
            low[node] = Math.min(low[node], low[next]);

            // 루트가 아니고, 자식의 low값이 자신의 발견 시간 이상이면 절단점
            if (parent != -1 && low[next] >= disc[node]) {
                isArticulation[node] = true;
            }

            // 다리 판별: low[next] > disc[node]
            if (low[next] > disc[node]) {
                System.out.println("Bridge: " + node + " - " + next);
            }
        } else if (next != parent) {
            low[node] = Math.min(low[node], disc[next]);
        }
    }

    // 루트이면서 자식이 2개 이상이면 절단점
    if (parent == -1 && children > 1) {
        isArticulation[node] = true;
    }
}

백엔드/실무에서의 연결

Spring Bean 순환 의존성 탐지

Spring IoC 컨테이너는 Bean 의존성 그래프를 구성합니다. 이 그래프에 사이클이 있으면 순환 의존성입니다.

JAVA

// 순환 의존성 예시
@Service
public class ServiceA {
    private final ServiceB serviceB;

    public ServiceA(ServiceB serviceB) { // ServiceB가 필요
        this.serviceB = serviceB;
    }
}

@Service
public class ServiceB {
    private final ServiceA serviceA;

    public ServiceB(ServiceA serviceA) { // ServiceA가 필요 → 사이클!
        this.serviceA = serviceA;
    }
}

Spring Boot 2.6부터는 생성자 주입에서의 순환 의존성을 기본적으로 금지합니다. 내부적으로 Bean 생성 과정에서 DFS 기반 사이클 탐지를 수행합니다.

패키지 의존성 분석

Maven/Gradle의 의존성 트리는 방향 그래프입니다. 순환 의존성이 있으면 빌드가 불가능합니다.

데드락 탐지

데이터베이스의 데드락 탐지는 ** 대기 그래프(Wait-for Graph)**에서의 사이클 탐지입니다. 트랜잭션이 노드, 대기 관계가 간선이 됩니다.

마이크로서비스 호출 그래프

MSA에서 서비스 간 호출 관계를 그래프로 표현하면, SCC 분석으로 강하게 결합된 서비스 그룹을 식별할 수 있습니다.

주의할 점

방향 그래프에서 visited만으로 사이클을 판단하는 실수

무방향 그래프에서는 visited 배열만으로 사이클을 탐지할 수 있지만, 방향 그래프에서는 ** 현재 DFS 경로에 있는 노드 **를 별도로 추적해야 합니다. visited만 체크하면 cross edge를 back edge로 오인하여 잘못된 사이클 탐지를 합니다.

재귀 DFS에서 스택 오버플로우

그래프 크기가 수만 이상이면 재귀 DFS에서 StackOverflowError가 발생할 수 있습니다. 명시적 스택을 사용한 반복문 DFS로 변환하는 것이 안전합니다.

정리

기법	용도	핵심 아이디어
사이클 탐지	순환 의존성, 데드락	3가지 상태(미방문/진행중/완료)로 back edge 감지
SCC (Kosaraju)	강결합 그룹 식별	종료 시간 역순 + 역방향 그래프 DFS
절단점/다리	네트워크 취약점	low값과 discovery time 비교

기억할 포인트:

DFS에서 back edge = 사이클 입니다. 노드 상태를 3가지로 관리하세요.
무방향 그래프에서는 부모 노드를 제외하고 사이클을 판단합니다.
SCC는 방향 그래프에서 양방향 도달 가능한 최대 그룹입니다.
Spring의 순환 의존성 탐지, DB 데드락 탐지 모두 그래프 사이클 탐지의 응용입니다.