알고리즘 : BFS (너비 우선 탐색)

너비우선탐색 (BFS)

 

• Breadth-First Search
• 그래프 or 트리의 한 노드에서 탐색 시작. 인접한 모든 노드를 먼저 탐색한 후 그 다음 인접 노드를 탐색하는 방식
• 한 레벨 씩 확장해가며 탐색하는 방식!

 

 

 

 

동작 원리

 

1. 시작 노드를 큐에 넣고, 해당 노드 방문 처리
   
   
2. (1) 큐에서 노드를 하나 꺼냄
   (2) 방문 처리
   (3) 꺼낸 노드의 인접 노드를 모두 큐에 추가함
   
   
3. 큐가 빌 때까지 반복
   
   

 

 

 

BFS가 필요한 상황?

1. 최단 경로 탐색 : 같은 level을 모두 방문한 후 다음 level로 이동하므로, 최단 경로를 확실하게 탐색할 수 있다.

 

2. 모든 노드 탐색 : 시작 노드가 속한 모든 그래프, 트리의 연결 여부를 확인할 수 있음

 

3. 웹 크롤링 : 특정 페이지에서 연결된 페이지를 모두 방문할 때

 

 

장점

• 최단 경로 보장
  
  
• 계층 구조 탐색에 적합

 

단점

• 메모리 사용이 DFS에 비해 크다.
  
  
• 모든 노드를 깊이에 관계 없이 탐색하므로, 깊이 있는 노드를 우선 탐색해야할 때에는 비효율적일 수 있다.

 

 

 

구현

큐를 이용한 구현

import java.util.*;

public class BFSQueue {
    // 큐를 이용한 BFS 알고리즘 구현
    public static void bfsQueue(Map<Integer, List<Integer>> graph, int startNode) {
        Queue<Integer> queue = new LinkedList<>();
        Set<Integer> visited = new HashSet<>();
        
        // 시작 노드를 큐에 추가하고 방문 처리
        queue.add(startNode);
        visited.add(startNode);
        
        while (!queue.isEmpty()) {
            int node = queue.poll();  // 큐에서 노드를 꺼냄
            System.out.print(node + " ");  // 방문한 노드를 출력
            
            // 인접한 모든 노드를 탐색
            for (int neighbor : graph.get(node)) {
                if (!visited.contains(neighbor)) {
                    queue.add(neighbor);  // 인접 노드를 큐에 추가
                    visited.add(neighbor);  // 방문 처리
                }
            }
        }
    }

    public static void main(String[] args) {
        // 그래프 초기화
        Map<Integer, List<Integer>> graph = new HashMap<>();
        graph.put(1, Arrays.asList(2, 3, 4));
        graph.put(2, Arrays.asList(1, 5, 6));
        graph.put(3, Arrays.asList(1, 7, 8));
        graph.put(4, Arrays.asList(1, 9));
        graph.put(5, Arrays.asList(2));
        graph.put(6, Arrays.asList(2));
        graph.put(7, Arrays.asList(2, 10));
        graph.put(8, Arrays.asList(3));
        graph.put(9, Arrays.asList(4));
        graph.put(10, Arrays.asList(7));

        bfsQueue(graph, 1);  // 1번 노드에서 BFS 시작
    }
}