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

너비 우선 탐색(BFS)은 그래프 탐색 알고리즘으로, 그래프의 정점과 간선을 체계적으로 탐색합니다. 루트 노드에서 시작해 현재 깊이의 모든 노드를 방문한 뒤에 다음 깊이로 이동하기 때문에, 레벨별로 경로를 탐색할 수 있으며 가중치가 없는 그래프에서 최단 경로를 발견하거나 연결 요소를 확인하는 데 강력한 기술입니다.

 

핵심 개념:

• 그래프는 정점(노드)과 이를 연결하는 간선으로 구성됩니다.
• 인접 리스트: 그래프를 표현하는 흔한 방법으로, 각 정점이 자신의 이웃 정점을 리스트 형태로 저장합니다.
• 큐: BFS는 큐를 이용해 탐색할 정점을 관리합니다. 큐는 선입선출(FIFO) 방식으로 동작하여, 탐색 순서를 유지합니다.

BFS의 동작 원리:

1. 초기화: 특정 시작 정점에서 시작합니다. 이 정점을 방문했다고 표시하고 큐에 추가합니다.
2. 탐색:
   • 큐에서 정점을 하나 꺼냅니다.
   • 해당 정점의 방문하지 않은 모든 이웃을 탐색합니다. 방문하지 않았다면 방문했다고 표시하고 큐에 추가합니다.
3. 종료 조건: 큐가 비게 되면 탐색을 종료합니다.

상세한 설명:

• 1단계: 시작 정점 선택
  A와 같은 특정 시작 정점에서 시작합니다. A를 "방문함"으로 표시하고 저장합니다.
• 2단계: 큐에 정점 추가
  A를 큐에 넣습니다. 이 큐는 탐색할 정점의 순서를 관리합니다.
• 3단계: 큐를 사용하여 정점 처리
  큐가 비어 있지 않은 동안, 큐의 맨 앞에 있는 정점을 꺼냅니다.
  해당 정점의 모든 이웃을 확인합니다:
  • 방문하지 않은 경우, 방문 처리하고 큐에 추가합니다.
• 4단계: 탐색 완료
  큐가 비거나 특정 조건(예: 목표 정점 발견)을 만족하면 탐색을 종료합니다.

BFS의 특징:

• BFS는 깊이 kkk의 모든 노드를 탐색한 후, 깊이 k+1로 이동합니다.
• 그래프가 가중치가 없는 경우, BFS는 시작점에서 모든 다른 노드로의 최단 경로를 보장합니다.

코드 구현

Java 코드 예제

import java.util.*;

public class BFSExample {
    public static void bfs(Map<Integer, List<Integer>> graph, int start) {
        // 큐와 방문 목록 초기화
        Queue<Integer> queue = new LinkedList<>();
        Set<Integer> visited = new HashSet<>();

        // 시작 노드를 방문 처리 후 큐에 추가
        visited.add(start);
        queue.add(start);

        // 큐가 비어있지 않는 동안 탐색 진행
        while (!queue.isEmpty()) {
            // 큐의 첫 번째 노드 꺼내기
            int currentNode = queue.poll();
            System.out.println("방문한 노드: " + currentNode);

            // 인접한 노드 탐색
            for (int neighbor : graph.getOrDefault(currentNode, new ArrayList<>())) {
                if (!visited.contains(neighbor)) {
                    visited.add(neighbor);  // 방문 처리
                    queue.add(neighbor);   // 큐에 추가
                }
            }
        }
    }

    public static void main(String[] args) {
        // 그래프 생성 (인접 리스트 방식)
        Map<Integer, List<Integer>> graph = new HashMap<>();
        graph.put(0, Arrays.asList(1, 2));
        graph.put(1, Arrays.asList(2, 3));
        graph.put(2, Arrays.asList(4));
        graph.put(3, Arrays.asList(4));
        graph.put(4, Arrays.asList());

        // BFS 실행
        System.out.println("BFS 탐색 결과:");
        bfs(graph, 0);
    }
}

 

코드 설명:

1. 그래프 표현:
   • 인접 리스트로 그래프를 표현하여 각 노드의 이웃 노드 리스트를 저장합니다.
2. 큐와 방문 세트 초기화:
   • Queue를 사용해 탐색 순서를 관리하고, Set을 이용해 방문한 노드를 추적합니다.
3. BFS 탐색 과정:
   • 큐에서 노드를 꺼내고, 그 노드의 이웃 노드 중 아직 방문하지 않은 노드를 큐에 추가합니다.
   • 큐가 빌 때까지 반복합니다.

---

Python 코드 예제

from collections import deque

def bfs(graph, start):
    # 방문 여부를 추적하기 위한 집합
    visited = set()
    # 탐색할 노드를 관리하기 위한 큐
    queue = deque([start])
    visited.add(start)

    while queue:
        # 큐에서 노드 꺼내기
        current_node = queue.popleft()
        print(f"방문한 노드: {current_node}")

        # 인접 노드 탐색
        for neighbor in graph.get(current_node, []):
            if neighbor not in visited:
                visited.add(neighbor)  # 방문 처리
                queue.append(neighbor)  # 큐에 추가

# 예제 실행
if __name__ == "__main__":
    # 그래프 생성 (인접 리스트 방식)
    graph = {
        0: [1, 2],
        1: [2, 3],
        2: [4],
        3: [4],
        4: []
    }

    # BFS 실행
    print("BFS 탐색 결과:")
    bfs(graph, 0)

 

코드 설명:

1. 그래프 표현:
   • 딕셔너리로 그래프를 표현하며, 각 노드의 이웃 리스트를 키-값 쌍으로 저장합니다.
2. 큐와 방문 세트 초기화:
   • deque를 사용해 탐색 순서를 관리하고, set으로 방문한 노드를 추적합니다.
3. BFS 탐색 과정:
   • 큐에서 노드를 꺼내고, 그 노드의 이웃 중 아직 방문하지 않은 노드를 큐에 추가하며 탐색을 계속합니다.

---

BFS의 특성 요약

특성설명

탐색 방식	레벨별로 그래프를 탐색
데이터 구조	큐를 사용하여 탐색 순서를 관리
시간 복잡도	O(V + E)O, V: 정점 수, E: 간선 수
공간 복잡도	방문 표시와 큐를 위한 O(V) 공간
대표적 사용 사례	무방향 그래프에서 최단 경로 찾기, 연결 요소 확인