가장 일반적인 그래프 탐색 알고리즘 둘을 비교해보자.

구현 방식

BFS는 큐를 통해 구현한다.

DFS는 재귀를 통해 구현하나, 스택으로도 구현할 수 있다. 어떤게 더 나은지는 상황에 따라 다르다.

사용 목적

• 가장 짧은 경로를 빠르게 하나만 찾아도 되는 경우

일반적으로 BFS를 사용한다. DFS는 틀린 경로도 일단은 탐색하기 때문에, 직감적으로도 BFS더 빠르다.

• 모든 경우의 수를 찾아야 하는 경우

DFS(백트래킹)을 사용하는게 낫다. BFS로도 불가능한건 아닌데 큐의 크기가 너무 커진다는 문제가 있고, BFS나 DFS나 결과 산출 속도가 같다.

• 트리의 깊이가 무한대인 경우(= 루프가 있는 경우), 정답이 아닌데 아주 긴 루트가 있는 경우

DFS로 답을 낼 수가 없거나 너무 비효율적이다. 전자의 경우 visited같은 다른 장치를 넣을 수는 있겠는데, 그럴거면 그냥 BFS 쓰는게 낫다. 후자의 경우 비효울적이며 스택 오버플로우가 발생할 수 있다.

그런데 역으로, 루프의 존재를 확인해야 한다면 DFS를 사용할 수 있다. 단, 가중치가 있다면 DFS나 BFS를 쓸게 아니라 벨만-포드 혹은 다익스트라 같은 알고리즘을 써야한다.