BFS(Breadth First Search)
BFS란 graph(다차원 배열)에서 인접 노드를 방문할 때 깊이보다 너비를 우선으로 방문하는 알고리즘이다.
BFS를 사용하면, 최단거리를 찾을 때 좋으며 거리를 잴 수 있다.
이 점을 고려하면 FIFO의 특성을 가진 queue를 이용해 아래와 같은 방법으로 구현할 수 있다.
- 시작 노드를 queue에 집어넣는다.
- queue의 front를 pop하여 해당 노드에 연결된 노드를 모두 체크하고 queue에 넣는다.
- 다시 front를 pop하여 위와 같은 작업을 한다.
- 위의 작업을 queue가 완전히 빌 때 까지 반복적으로 한다.
예시)
- 위와 같은 그래프를 생각해보자. 시작 노드를 0이라고 할 때, 0을 queue에 집어놓고 pop을하며 0과 이어져있는 2,1,5를 순서대로 queue에 집어넣는다.
- 다시 pop을하면 2가 나오게되고, 2와 연결된 4,3을 queue에 집어넣는다.
- 다음번 pop은 1이 나오게되고, 1과 연결된 노드는 2뿐이다. 하지만 2는 이미 방문했기 때문에 다시 넣으면 무한루프가 돌게된다. 따라서 한 번 방문한 노드는 방문했다는 표시를 해주어야 한다. 이때 방문 표시는 queue에서 뺄때가 아니라 넣을때 해주어야함
- 해당 작업을 마치면 0-2-1-5-4-3 순으로 방문을 마칠것이다.
보통 인접리스트로 구현된 BFS의 Time Complexity는 O(N + E) 이다. (노드의 개수 + edged list(간선)의 개수)