위키득계정 ↗
기술

BFS와 DFS의 차이

BFS와 DFS의 차이기술
BFS
같은 거리 단계부터 탐색
DFS
한 경로를 깊게 탐색
대표 상태 구조
큐와 스택
거리 조건
BFS의 간선 수 최단 거리는 무가중 조건
너비 우선 탐색은 시작점에서 가까운 단계부터, 깊이 우선 탐색은 한 경로를 깊게 따라가며 그래프를 방문한다. 탐색 순서와 기억할 상태가 다르므로 거리 계산이나 구조 분석 등 목적에 맞게 선택해야 한다.

방문 순서가 다른 이유

시작점의 이웃을 먼저 모두 살핀 뒤 다음 단계로 가면 너비 우선 탐색의 구조가 된다. 한 이웃을 택해 더 이상 진행하지 못할 때까지 내려간 뒤 돌아오면 깊이 우선 탐색의 구조가 된다. 이웃을 어떤 순서로 보느냐에 따라서도 구체적인 방문 순서는 달라질 수 있다. 탐색 방식과 정점 이름 순서는 같은 기준이 아니다.

가까운 경로를 찾는 경우

모든 간선의 비용을 같게 보거나 간선 수만 세는 문제에서는 BFS로 시작점에서의 최단 거리를 구할 수 있다. 처음 도달한 단계가 최소 간선 수가 되기 때문이다. 간선별 비용이 다르면 단계 수가 적은 경로가 비용까지 작다고 보장할 수 없다. 가중치를 무시한 BFS와 가중 최단 경로 문제를 구분해야 한다.

깊게 찾았다는 사실

DFS에서 처음 발견한 목적지까지의 경로가 항상 가장 짧지는 않다. A에서 D로 직접 가는 간선이 있어도 이웃 순서에 따라 A에서 B, C를 거쳐 D를 먼저 찾을 수 있다. 깊이 있게 탐색하는 방식은 구조 분석에 유용하지만 처음 발견했다는 사실의 의미를 목적에 맞게 해석해야 한다.

방문 상태의 수명

그래프에 순환이 있으면 이미 처리한 정점을 구분하지 않을 때 같은 경로를 반복할 수 있다. 전역적으로 방문했는지와 현재 경로에 포함되어 있는지는 서로 다른 정보다. 순환 검사나 경로 열거에서는 필요한 상태가 달라질 수 있다. 방문 표시 하나를 모든 탐색 문제에 같은 방식으로 적용하지 않는다.

실행 환경의 한계

DFS를 재귀로 구현하면 깊은 입력에서 호출 깊이 제한을 만날 수 있다. 명시적인 스택을 사용할지 검토하고 BFS에서도 한 단계에 많은 정점이 몰리는 경우의 메모리를 살핀다. 자료구조를 선택한 뒤에는 연결되지 않은 정점과 고립 정점도 필요한 범위만큼 처리하는지 확인한다.

관련 문서

너비 우선 탐색 / 깊이 우선 탐색 / 알고리즘