그래프 사이클 탐지 — 순환 의존성을 찾아내는 알고리즘

public class DirectedCycleDetection {
    private static final int WHITE = 0, GRAY = 1, BLACK = 2;

    public boolean hasCycle(List<List<Integer>> graph, int n) {
        int[] color = new int[n]; // 모두 WHITE로 시작

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

    private boolean dfs(List<List<Integer>> graph, int u, int[] color) {
        color[u] = GRAY; // 탐색 시작

        for (int v : graph.get(u)) {
            if (color[v] == GRAY) {
                return true; // 사이클 발견!
            }
            if (color[v] == WHITE && dfs(graph, v, color)) {
                return true;
            }
            // BLACK은 이미 탐색 완료 → 무시
        }

        color[u] = BLACK; // 탐색 완료
        return false;
    }
}

정상:  A(GRAY) → B(GRAY) → C(GRAY) → D(BLACK)  ← BLACK이므로 사이클 아님
사이클: A(GRAY) → B(GRAY) → C(GRAY) → A(GRAY)   ← GRAY이므로 사이클!

// 사이클 경로 복원
private List<Integer> cyclePath;
private int[] parent;

private boolean dfsWithPath(List<List<Integer>> graph, int u, int[] color) {
    color[u] = GRAY;

    for (int v : graph.get(u)) {
        if (color[v] == GRAY) {
            // 사이클 경로 복원
            cyclePath = new ArrayList<>();
            cyclePath.add(v);
            int curr = u;
            while (curr != v) {
                cyclePath.add(curr);
                curr = parent[curr];
            }
            cyclePath.add(v);
            Collections.reverse(cyclePath);
            return true;
        }
        if (color[v] == WHITE) {
            parent[v] = u;
            if (dfsWithPath(graph, v, color)) return true;
        }
    }

    color[u] = BLACK;
    return false;
}

public boolean hasCycleKahn(List<List<Integer>> graph, int n) {
    int[] inDegree = new int[n];

    // 진입 차수 계산
    for (int u = 0; u < n; u++) {
        for (int v : graph.get(u)) {
            inDegree[v]++;
        }
    }

    // 진입 차수 0인 노드 큐에 추가
    Queue<Integer> queue = new LinkedList<>();
    for (int i = 0; i < n; i++) {
        if (inDegree[i] == 0) queue.offer(i);
    }

    int processed = 0;
    while (!queue.isEmpty()) {
        int u = queue.poll();
        processed++;
        for (int v : graph.get(u)) {
            inDegree[v]--;
            if (inDegree[v] == 0) queue.offer(v);
        }
    }

    // 처리된 노드 수 < 전체 → 사이클 존재
    return processed < n;
}

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

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

private boolean dfsUndirected(List<List<Integer>> graph, int u, int parent, boolean[] visited) {
    visited[u] = true;

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

public class UnionFindCycle {
    private int[] parent, rank;

    public boolean hasCycle(int n, int[][] edges) {
        parent = new int[n];
        rank = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;

        for (int[] edge : edges) {
            int rootU = find(edge[0]);
            int rootV = find(edge[1]);

            if (rootU == rootV) return true; // 사이클!
            union(rootU, rootV);
        }
        return false;
    }

    private int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]); // 경로 압축
        return parent[x];
    }

    private void union(int a, int b) {
        if (rank[a] < rank[b]) { int t = a; a = b; b = t; }
        parent[b] = a;
        if (rank[a] == rank[b]) rank[a]++;
    }
}

// 순환 참조 예시
@Component
public class ServiceA {
    private final ServiceB serviceB;
    public ServiceA(ServiceB serviceB) { this.serviceB = serviceB; }
}

@Component
public class ServiceB {
    private final ServiceA serviceA;
    public ServiceB(ServiceA serviceA) { this.serviceA = serviceA; }
}
// → BeanCurrentlyInCreationException 발생!

module-a → module-b → module-c → module-a  (순환!)