BFS 알고리즘 개념

DFS에 이어서 BFS 개념 보기

DFS는 트리 행부터 탐색(=세로로 탐색)하는 반면
BFS는 트리 열부터 탐색(=가로로 탐색) 하는 방법 입니다.

 

구현 부분에서는 DFS랑 다를게 없습니다. 단지, Stack -> Queue로 변경되는 것 뿐이죠.

 

----------------------오늘의 요약 정리 ---------------------

BFS 알고리즘 순서!
1. Queue에 있는 노드를 꺼내 출력한다.
2. 방금 꺼낸 노드의 자식들을 Queue에 Add 한다.
3. Queue가 비어있지 않다면 1번으로 이동

---------------------------------------------------------------

 

 

바로 그림으로 정리하겠습니다.

이진 트리 BFS 순회는 아래 트리를 이용해서 진행하겠습니다.

그림 1. 예제로 사용 할 이진 트리

 

 

 

 

시작

알고리즘 순서는 간단합니다.

1. Queue에 있는 노드를 꺼내 출력한다.
2. 방금 꺼낸 노드의 자식들을 Queue에 Add 한다.
3. Queue가 비어있지 않다면 1번으로 이동

 

 

1부터 방문할 것이기 때문에 1을 Queue에 삽입한 상태로 시작합니다.

그림 1. BFS 탐색(1)

 

 

 

 

1. Queue에 있는 노드를 하나 꺼내면서 출력합니다.

그림 2. BFS 탐색(2)

 

 

 

2. 노드 1을 방문처리 하고, 1의 자식 노드를 Queue에 삽입한다.

 

그림 3. BFS 탐색(3)

 

 

 

3. 자식노드 2,3을 방문처리 후 Queue에서 하나 꺼내 출력합니다.

그림 4. BFS 탐색(4)

 

 

 

 

4. 꺼낸 노드 2의 자식들을 Queue에 삽입 합니다.

그림 5. BFS 탐색(5)

 

 

 

5. Queue에 삽입한 노드를 방문처리 후 Queue에서 다시 하나 꺼내 출력 합니다.

그림 6. BFS 탐색(6)

 

 

 

 

6. 꺼낸 3의 자식노드를 Queue에 삽입한다.

그림 7. BFS 탐색(7)

 

 

 

 

7. 삽입한 노드를 방문처리 후 Queue에 있는 노드(4)를 하나 꺼내 출력합니다.

그림 8. BFS 탐색(8)

 

 

 

 

8. 자식노드가 없기때문에 다시 Queue에서 노드(5)를 하나 꺼내서 출력합니다.

그림 9. BFS 탐색(9)

 

 

 

 

9. 5는 자식이 없기때문에 Queue에서 다음 노드(6)을 꺼내 출력합니다.

그림 10. BFS 탐색(10)

 

 

 

 

 

10. 6은 자식 노드가 없기 때문에 Queue에서 다음 노드(7)를 꺼내서 출력합니다.

그림 11. BFS 탐색(11)

 

 

 

 

 

(마지막)11. Queue에 더이상 값이 없으므로, 탐색을 종료합니다!

그림 12. BFS 탐색(12)

 

 

이렇듯 BFS 탐색에 대해 알아보았습니다.

알고리즘 순서만 지킨다면 어렵지 않은 알고리즘입니다.

 

코드로 구현하는 것은 아래 링크로 연결하겠습니다!

https://mr-dan.tistory.com/45