너비 우선 탐색(BFS)

1. 너비 우선 탐색(BFS)이란?

- BFS(Breadth-First-Search) 알고리즘으로 그래프나 트리에서 시작 정점으로부터 인접한 노드들을 먼저 탐색한 후 그 다음 단계(레벨)

- 시작 정점 부터 인접한 모든 노드를 방문하고 방문한 인접 노드를 그 다음 순서로 탐색하는 계층적 탐색 기법이다.

- 탐색 순서를 관리하기 위해 FIFO(First-In-First-Out) 방식의 큐를 사용하며, 각 단계별로 노드를 처리한다.

 

1-1. BFS의 장단점

• 장점
  • 최단 경로 탐색: 가중치가 동일한 그래프에서 시작 정점으로부터의 최단 경로를 보장한다.
  • 레벨 정보 획득: 각 노드가 몇 번째 레벨에 있는지 쉽게 파악 할 수 있다.
• 단점
  • 메모리 사용: 큐에 모든 인접 노드가 저장되므로 매우 넓은 그래프에서는 메모리 사용량이 많아질 수 있다.
  • 대규모 그래프: 그래프의 정점이나 간선 수가 매우 많을 경우 실행 시간이 길어질 수 있다.

 

1-2. BFS 활용 분야

- 최단 경로 탐색: 무가중치 그래프에서 시작 정점부터 다른 정점까지의 최단 경로를 찾을 때 사용한다.

- 레벨 순회: 트리의 각 레벨별로 노드를 방문하거나 깊이(레벨) 정보를 추출할 때 유용하다.

- 연결 요소 탐색: 그래프 내 모든 정점을 방문하여 연결된 구성 요소를 파악하는데 사용된다.

- 사이클 검출 및 이분 그래프 판별: BFS를 통해 그래프의 구조를 분석하여 사이클 여부나 이분성을 판별할 수 있다.

 

2. BFS 알고리즘 구현

- BFS는 일반적으로 Queue를 사용하여 구현한다.

public class BFSExample {
    // 그래프를 인접 리스트로 표현 (정점 번호: 0부터 시작)
    private Map<Integer, List<Integer>> graph;

    public BFSExample() {
        graph = new HashMap<>();
    }

    // 무방향 그래프에 간선 추가
    public void addEdge(int src, int dest) {
        graph.computeIfAbsent(src, x -> new ArrayList<>()).add(dest);
        graph.computeIfAbsent(dest, x -> new ArrayList<>()).add(src);
    }

    // BFS 알고리즘: 시작 정점부터 너비 우선 탐색을 수행
    public void bfs(int start) {
        Set<Integer> visited = new HashSet<>();
        Queue<Integer> queue = new LinkedList<>();

        visited.add(start);
        queue.offer(start);

        while(!queue.isEmpty()) {
            int current = queue.poll();
            System.out.print(current + " ");

            for(int neighbor : graph.getOrDefault(current, new ArrayList<>())) {
                if (!visited.contains(neighbor)) {
                    visited.add(neighbor);
                    queue.offer(neighbor);
                }
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BFSExample bfsExample = new BFSExample();

        // 예제 그래프 구성
        // 그래프 구조:
        //         0
        //       /   \
        //      1     2
        //     / \   / \
        //    3   4 5   6
        bfsExample.addEdge(0, 1);
        bfsExample.addEdge(0, 2);
        bfsExample.addEdge(1, 3);
        bfsExample.addEdge(1, 4);
        bfsExample.addEdge(2, 5);
        bfsExample.addEdge(2, 6);

        // 출력: 0 1 2 3 4 5 6
        bfsExample.bfs(0);
    }
}