너비 우선 탐색

너비 우선 탐색(Breadth-First Search, BFS)은 그래프 탐색 알고리즘 중 하나로, 루트 노드에서 시작하여 인접한 노드를 먼저 탐색한 후 점차 멀리 있는 노드를 탐색하는 방식이다.

BFS와 DFS

1 알고리즘

너비 우선 탐색은 일반적으로 큐(Queue)를 사용하여 구현된다. 기본적인 과정은 다음과 같다.

1. 탐색을 시작할 노드를 큐에 삽입하고 방문 표시를 한다.
2. 큐에서 노드를 꺼내 해당 노드의 인접 노드들을 확인한다.
3. 방문하지 않은 인접 노드를 큐에 삽입하고 방문 표시를 한다.
4. 큐가 빌 때까지 위 과정을 반복한다.

2 예제 코드

다음은 Python을 사용한 너비 우선 탐색 구현 예제이다.

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    visited.add(start)
    
    while queue:
        node = queue.popleft()
        print(node, end=' ')
        
        for neighbor in graph[node]:
            if neighbor not in visited:
                queue.append(neighbor)
                visited.add(neighbor)

# 그래프 예제
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F', 'G'],
    'D': ['B'],
    'E': ['B'],
    'F': ['C'],
    'G': ['C']
}

bfs(graph, 'A')

3 특성

• 최단 경로 보장: 무가중 그래프에서 시작 노드로부터 특정 노드까지의 최단 경로를 찾을 수 있다.
• 시간 복잡도: O(V + E) (V는 정점 개수, E는 간선 개수)
• 공간 복잡도: O(V)

4 활용

• 최단 경로 탐색 (예: GPS 네비게이션, 미로 찾기)
• 네트워크에서 데이터 탐색
• 웹 크롤링
• AI의 상태 공간 탐색 (예: 체스, 퍼즐 문제 해결)

5 같이 보기

• 깊이 우선 탐색
• 다익스트라 알고리즘
• A* 알고리즘

6 참고 문헌

• Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms. MIT Press.