[알고리즘] BFS 너비 우선 탐색

너비 우선 탐색 Breadth-First Search

그래프를 완전 탐색하는 방법 중 하나

시작 노드에서 출발해 시작 노드를 기준으로 가까운 노드를 먼저 방문하면서 탐색하는 알고리즘

FIFO 선입선출 방식으로 탐색하므로 Queue 자료구조 이용하는 특징을 가지고 있다

O(노드 수 V + 에지 수 E)의 시간 복잡도를 가진다

탐색 시작 노드와 가까운 노드를 우선하여 탐색하므로 목표 노드에 도착하는 경로가 여러 개일 때 최단 경로를 보장

 

BFS 동작

방문했던 노드는 다시 방문하지 않으므로 방문한 노드를 체크하기 위한 배열 필요

그래프를 인접 리스트로 표현

탐색을 위해 스택이 아닌 큐를 사용

 

1. BFS를 시작할 노드를 정한 후 사용할 자료구조 초기화

 

BFS를 위해 필요한 초기 작업

1. 인접 리스트로 그래프 표현하기
2. 방문 배열 초기화하기
3. 시작 노드 큐에 삽입하기

 

 2. 큐에서 노드를 꺼낸 후 꺼낸 노드의 인접 노드를 다시 큐에 삽입하기

큐에서 노드를 꺼내면서 인접 노드를 큐에 삽입

이때 방문 배열을 체크하여 이미 방문한 노드는 큐에 삽입하지 않는다

큐에서 꺼낸 노드는 탐색 순서에 기록

 

3. 큐 자료구조에 값이 없을 때까지 반복

큐에 노드가 없을 때까지 과정 반복

 

DFS 탐색 순서 ▶ 1 → 3 → 4 → 6 → 2 → 5

BFS 탐색 순서 ▶ 1 → 2 → 3 → 5 → 6 → 4

같은 그래프여도 탐색 순서가 다르다

 

 

관련 문제 보기

백준 2178번 미로 탐색