BFS (Breadth-First Search) [너비 우선 탐색]

1. 핵심 개념 요약

• 탐색 방식: 너비 우선 (가까운 노드부터)

• 자료구조: 큐(Queue) 사용

• 사용 목적: 최단 거리, 레벨 탐색 등에 적합

• 방문 순서: 현재 노드 → 인접한 노드들 순차 방문

2. 동작 원리

1. 시작 노드를 큐에 삽입하고 방문 처리

2. 큐에서 노드를 꺼내고, 인접한 노드들을 확인

3. 아직 방문하지 않은 노드는 큐에 추가하고 방문 처리

4. 큐가 빌 때까지 반복

3. 예제 코드 (Java)

import java.util.*;

public class BFSExample {
    // BFS 탐색 함수
    public static void bfs(int start, List<List<Integer>> graph, boolean[] visited) {
        Queue<Integer> queue = new LinkedList<>(); // 탐색할 노드를 담을 큐 생성
        queue.offer(start); // 시작 노드를 큐에 추가
        visited[start] = true; // 시작 노드를 방문 처리

        while (!queue.isEmpty()) { // 큐가 빌 때까지 반복
            int node = queue.poll(); // 큐에서 노드 꺼내기
            System.out.print(node + " "); // 현재 노드 출력 (방문 순서)

            // 현재 노드와 연결된 모든 인접 노드를 탐색
            for (int neighbor : graph.get(node)) {
                if (!visited[neighbor]) { // 아직 방문하지 않은 노드인 경우
                    queue.offer(neighbor); // 큐에 추가
                    visited[neighbor] = true; // 방문 처리
                }
            }
        }
    }

    public static void main(String[] args) {
        // 그래프 초기화 (인덱스 1부터 사용하기 위해 크기 6+1)
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < 7; i++) {
            graph.add(new ArrayList<>());
        }

        // 무방향 그래프 연결 정보 설정
        graph.get(1).addAll(Arrays.asList(2, 3)); // 1번 노드 → 2, 3
        graph.get(2).addAll(Arrays.asList(4, 5)); // 2번 노드 → 4, 5
        graph.get(3).add(5);                      // 3번 노드 → 5
        graph.get(4).add(6);                      // 4번 노드 → 6
        graph.get(5).add(6);                      // 5번 노드 → 6

        boolean[] visited = new boolean[7]; // 방문 배열 초기화 (false 기본값)
        bfs(1, graph, visited); // 1번 노드부터 BFS 시작
    }
}

출력 예시

1 2 3 4 5 6

4. 특징

• 시간 복잡도: O(V + E)
(V: 노드 수, E: 간선 수)

• 공간 복잡도: O(V)
(방문 여부 확인 + 큐 공간)

• 장점: 최단 경로 보장 (가중치 없는 그래프에서)

• 단점: 큐 공간 많이 사용 → 메모리 부담

5. BFS vs DFS 비교