그래프 순회

그래프의 순회 (Graph Traversal)

그래프 순회는 그래프의 모든 정점을 한 번씩 방문하는 과정
대표적인 방식은 너비 우선 탐색(BFS) 과 깊이 우선 탐색(DFS) 이 있다.

1. 너비 우선 탐색 (BFS: Breadth-First Search)

BFS는 가까운 정점부터 차례로 탐색해 나가는 방식
큐(Queue) 자료구조를 이용해 구현한다.

BFS 알고리즘 흐름

1. 시작 정점을 큐에 추가
2. 큐가 빌 때까지 다음을 반복
    2-1. 큐에서 정점 꺼내 방문
    2-2. 연결된 미방문 정점을 큐에 추가

Set 사용

 

 

Map<Integer, List<Integer>> graph = Map.of(
    0, List.of(1, 3, 6),
    1, List.of(0, 3),
    2, List.of(3),
    3, List.of(0, 1, 2, 7),
    4, List.of(5),
    5, List.of(4, 6, 7),
    6, List.of(0, 5),
    7, List.of(3, 5)
);

Set<Integer> visited = new HashSet<>();
Queue<Integer> queue = new LinkedList<>();

void bfs(int start) {
    queue.add(start);
    visited.add(start);
    while (!queue.isEmpty()) {
        int cur = queue.poll();
        for (int next : graph.get(cur)) {
            if (!visited.contains(next)) {
                queue.add(next);
                visited.add(next);
            }
        }
    }
}

boolean[] 사용

 

boolean[] visited = new boolean[8]; // 정점 수
Queue<Integer> queue = new LinkedList<>();

void bfs(int start) {
    queue.add(start);
    visited[start] = true;
    while (!queue.isEmpty()) {
        int cur = queue.poll();
        for (int next : graph.get(cur)) {
            if (!visited[next]) {
                queue.add(next);
                visited[next] = true;
            }
        }
    }
}

 

2. 깊이 우선 탐색 (DFS: Depth-First Search)

DFS는 하나의 경로를 따라 최대한 깊이 내려간 후, 더 이상 갈 수 없을 때 이전으로 되돌아가며 탐색한다.
재귀 함수 또는 스택(Stack) 으로 구현할 수 있다.

DFS 알고리즘 흐름

1. 현재 정점 방문 표시
2. 연결된 정점 중 미방문 정점에 대해 재귀 호출

Set 사용

 

 

 

Set<Integer> visited = new HashSet<>();

void dfs(int cur) {
    visited.add(cur);
    for (int next : graph.get(cur)) {
        if (!visited.contains(next)) {
            dfs(next);
        }
    }
}

boolean[] 사용

 

boolean[] visited = new boolean[8];

void dfs(int cur) {
    visited[cur] = true;
    for (int next : graph.get(cur)) {
        if (!visited[next]) {
            dfs(next);
        }
    }
}

 

스택을 이용한 DFS (반복문 방식)

boolean[] visited = new boolean[8];
Deque<Integer> stack = new ArrayDeque<>();

void dfsIterative(int start) {
    stack.push(start);
    while (!stack.isEmpty()) {
        int cur = stack.pop();
        if (visited[cur]) continue;
        visited[cur] = true;
        for (int next : graph.get(cur)) {
            if (!visited[next]) {
                stack.push(next);
            }
        }
    }
}

 

3. 시간 복잡도

그래프 표현 방식	시간 복잡도
인접 리스트	O(V + E)
인접 행렬	O(V²)

• V: 정점 수
• E: 간선 수

* 희소 그래프에서는 인접 리스트가 효율적이며, 밀집 그래프에서는 두 방식이 유사할 수 있습니다.

4. DFS 재귀 vs 반복 비교

 

구현 방식	사용구조	장점	주의점
재귀 방식	시스템 스택	간결하고 직관적	재귀 깊이 초과 가능
반복 방식	명시적 스택	재귀 없이 안정적으로 실행 가능	코드가 길어짐

DFS 재귀 구현은 구조가 간단하지만, 호출 깊이가 깊을 경우 스택 오버플로우 발생 가능성이 있으므로 입력 크기에 따라 반복 방식으로 변경하는 것이 좋다.