BFS Algorithm Breadth-First-Search
너비 우선 탐색 알고리즘
너비 우선 탐색 알고리즘은 DFS
와 동일하게 그래프 완전 탐색 기법 중 하나로, 시작 노드에서 출발해 시작 노드를 기준으로 가까운 노드를 먼저 방문하여 탐색하는 알고리즘이다.
특징
FIFO
탐색
Queue
자료구조 활용
- 시간 복잡도 :
O(V + E)
구현 순서
1. BFS
를 시작할 노드를 정한 후 사용할 자료구조 초기화하기
2. Queue
에서 노드를 꺼낸 후, 꺼낸 노드의 인접 노드를 다시 Queue
에 삽입하기
-
Queue
에서 노드를 꺼내면서 인접 노드를 Queue
에 삽입하고, 방문 배열을 체크하여 이미 방문한 인접 노드에 대해 Queue
에 삽입한다. Queue
에서 꺼낸 노드는 탐색 순서에 기록한다.
-
1
를 꺼내면서, 인접 노드 node 2, 3
를 Queue
에 저장
3. Queue
에 값이 없을 때까지 반복하기
- 1 ~ 2 번 순서를
Queue
자료구조에 값이 없어질 때까지 반복한다. 이미 다녀간 노드는 역시 삽입하지 않는다.
node 2
를 꺼내면, 인접 노드 node 5, 6
를 Queue
에 저장 및 방문 배열 체크
node 3
를 꺼내면, 인접 노드 node 4
를 Queue
에 저장 및 방문 배열 체크
BFS
실행 순서
구현
출처