[알고리즘] 너비 우선 탐색(BFS, Breadth-First Search) 알고리즘

너비 우선 탐색 알고리즘이란?

너비 우선 탐색 알고리즘 특징

• 최단 경로 탐색: DFS와 달리 BFS는 최단 경로 탐색에 유리 (특히, 무가중치 그래프에서는 출발점에서 특정 정점까지의 최단 경로를 보장)

• 메모리 사용: 큐에 모든 이웃을 저장하기 때문에 메모리 사용량이 많음

• 평행적 확장: 출발점에서 가까운 정점부터 차례대로 탐색하기 때문에 일정한 깊이에서의 노드를 한 번에 탐색 가능

너비 우선 탐색 알고리즘 실제 적용 사례

• 최단 경로 탐색: 지하철 노선도와 같은 그래프 구조에서 두 역 간의 최단 경로를 찾는 데 사용

• 네트워크 탐색: BFS는 네트워크나 소셜 네트워크에서 특정 사용자로부터 다른 사용자까지 도달하는 경로를 찾는 데 자주 활용

• 웹 크롤링: BFS는 검색 엔진에서 페이지 간의 링크 구조를 따라가며 웹을 탐색하는 데 사용

너이 우선 탐색 알고리즘의 단계

너비 우선 탐색 구현 (ex. python)

### 입력 ###

from collections import deque

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

graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}
bfs(graph, 'A')

### 출력 ###
A B C D E F