싸이클 그래프 찾기

BFS(또는 DFS) 이용한 사이클 검출

기본 원리

• 방문 기록: 각 정점을 탐색하면서 방문 여부를 기록
• 부모 정보 관리: 현재 노드의 인접 노드를 탐색할 때, "바로 이전에 방문한 노드(부모)"는 제외. 무방향 그래프에서는 부모 노드와의 연결은 정상적 연결이기 때문

예제 코드 (BFS)

import java.util.*;

public class CycleDetectionBFS {
    public static boolean hasCycle(List<Integer>[] graph, int n) {
        boolean[] visited = new boolean[n];
        // 모든 연결 요소에 대해 BFS 수행
        for (int i = 0; i < n; i++) {
            if (!visited[i] && bfs(graph, i, visited)) {
                return true;
            }
        }
        return false;
    }

    private static boolean bfs(List<Integer>[] graph, int start, boolean[] visited) {
        Queue<int[]> queue = new LinkedList<>();
        // {현재 노드, 부모 노드}; 시작 노드는 부모가 없으므로 -1 사용
        queue.add(new int[] { start, -1 });
        visited[start] = true;

        while (!queue.isEmpty()) {
            int[] curInfo = queue.poll();
            int cur = curInfo[0];
            int parent = curInfo[1];

            for (int neighbor : graph[cur]) {
                if (neighbor == parent) continue; // 부모 노드는 무시
                if (visited[neighbor]) {
                    // 이미 방문된 노드인데 부모가 아니라면 싸이클
                    return true;
                }
                visited[neighbor] = true;
                queue.add(new int[] { neighbor, cur });
            }
        }
        return false;
    }
}

 

Union-Find(서로소 집합) 이용한 사이클 검출

기본 원리

• 초기화:
  • 각 정점을 자기 자신을 대표하는 집합으로 초기화
• Union 연산:
  • 만약 두 정점의 대표가 같다면, 이미 동일 집합에 속해 있으므로 이 간선을 추가하면 싸이클이 발생한 것
  • 서로 다른 집합이면 두 집합을 합칩니다. 이때 합치는 순서는 특별한 기준(예: 번호가 작은 쪽을 대표)으로 정할 수 있습니다
• 간선 (u, v) 가 주어질 때, 두 정점의 대표 노드를 찾는다
• 추가적으로 두 집합 중 하나라도 이미 싸이클이 발생한 집합이라면, 합쳐진 집합 역시 싸이클이 있는 집합

예제 코드 (Union-Find)

public class CycleDetectionUnionFind {
    int[] parent;
    boolean[] hasCycle;

    // 생성자: n개의 정점이 있다고 가정
    public CycleDetectionUnionFind(int n) {
        parent = new int[n];
        hasCycle = new boolean[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            hasCycle[i] = false; // 초기에는 싸이클이 없다고 가정
        }
    }

    // 경로 압축을 적용한 find 메서드
    public int find(int a) {
        if (parent[a] == a) return a;
        return parent[a] = find(parent[a]);
    }

    // union 연산: 두 노드를 합치고 싸이클 여부를 반영
    public void union(int a, int b) {
        int parentA = find(a);
        int parentB = find(b);

        // 만약 두 노드가 이미 같은 집합이면, 싸이클 발생!
        if (parentA == parentB) {
            hasCycle[parentA] = true;
            return;
        }

        // 두 집합 중 하나라도 싸이클이면 합친 집합에도 싸이클
        boolean cycleFlag = hasCycle[parentA] || hasCycle[parentB];

        // 대표를 번호가 작은쪽으로 결정 (단순한 기준)
        if (parentA < parentB) {
            parent[parentB] = parentA;
            hasCycle[parentA] = cycleFlag; // 싸이클 정보 전파
        } else {
            parent[parentA] = parentB;
            hasCycle[parentB] = cycleFlag;
        }
    }
}

 

BFS/DFS vs. Union-Find 비교

BFS / DFS	- 각 정점을 탐색하며 방문 여부 및 부모 정보를 관리 - 연결 요소 내부를 순회하며 싸이클 판별	- 그래프의 구조를 명시적으로 탐색할 때 - 문제에서 모든 경로를 탐색해야 하는 경우
Union-Find	- 각 정점을 독립 집합으로 시작하여, 간선 추가 시 집합을 합침 - 대표 노드를 통해 싸이클 판별	- 간선의 추가/삭제가 빈번한 동적 문제 - 연결 요소의 관리에 집중할 때

 

두 방법 모두 상황에 맞게 사용될 수 있으며, Union-Find는 특히 간선의 개수가 많거나 연결 여부를 빠르게 판별해야 할 때 효율적