[Do it! 알고리즘 코딩테스트 with Python] 너비 우선 탐색 (BFS)

너비 우선 탐색(BFS)

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

부모가 나가면 자식이 들어와 

기능	특징	시간 복잡도(노드 수: V, 에지 수: E)
그래프 완전 탐색	- FIFO 탐색 - Queue 자료구조 이용	O(V + E)

 

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

 

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

 

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

 

너비 우선 탐색(BFS) 구현 방법

다음과 같은 반복하면 'A-B-C-D-E-F-G-H-J' 가 된다.

1. (초기화) traversal ← 빈 리스트, q ← 빈 큐

2. 빈 트리가 아니면, root node를 q에 추가(enqueue)

3. q가 비어 있지 않은 동안

    3.1. node ← q에서 원소를 추출 (dequeue)

    3.2. node 를 방문

    3.3. node 의 왼쪽, 오른쪽 자식 (있으면)들을 q에 추가

4. q가 빈 큐가 되면 모든 노드 방문 완료