BFS

BFS는 한쪽 노드로 끝까지 들어가는 DFS와 다르게
간선이 있는 모든경우를 방문하며 레벨별로 그래프를 탐색하는 방법이다

DFS가 스택프레임의 스택을 이용하는것과 다르게
BFS는 큐를 이용한다

BFS가 동작하는 방식

0레벨 방문
큐에 먼저 루트노드 0을 넣는다(0 방문)

1레벨 방문
루트노드를 pop하고 루트노드에 연결되어있던 간선들을 모두 큐에 담는다(1,2 방문)
루트노드와 연결된 모든 노드를 큐에 넣고나면

2레벨 방문
1) 큐에서 pop을 하고 루트에 연결된 간선중 가장먼저 큐에 들어간 노드(1)가 나오게 된다. 이제 다시 큐에서 나온 노드(1)와 연결된 모든 간선들을 모두 큐에 담는다.
(3,4 방문)
2) 노드1과 연결된 모든 노드를 큐에 넣고나면
큐에서 pop을 하고 루트에 연결된 간선중 두번째로 큐에 들어간 노드(2)가 나오게 된다. 이제 다시 큐에서 나온 노드(2)와 연결된 모든 간선들을 모두 큐에 담는다.
(5,6 방문)

이런식으로 레벨별로 탐색이 되는것이 BFS다

BFS가 유리한 상황

BFS와 DFS 둘 다 순서만 다를뿐 경우의수는 동일하지만
BFS가 유리한상황은 인접노드를 순차적으로 탐색해야하는 상황이다

하나의 노드에서 갈수있는 최대 레벨이 무한하다면
DFS로 그래프를 탐색하면 탐색하다가 스택프레임의 메모리가 초과될것이다

또한 이런경우 DFS는 시작점에서 도착점으로 가는
거의 무한한 종류의 길을 모두 탐색해야 한다.

반면에 BFS는 도착점에 도달한 순간 끝내버리면 된다.

ex) 미로의 최단거리 찾기