BFS와 DFS의 차이

본 블로그 작성 글들은, 강의를 목표로 하고 제작되었습니다. 또한 작성된 글의 정보도 틀렸을 수 있으니, 주의해주세요.

그래프를 탐색하는 대표적인 방법에는 BFS와 DFS가 있다. 둘 다 방문하지 않은 정점을 따라가지만 순서가 다르다.

BFS

Breadth-First Search는 시작점에서 가까운 정점부터 넓게 탐색한다. Queue를 사용한다.

std::queue<int> Open;
std::vector<bool> Visited(NodeCount, false);

Open.push(Start);
Visited[Start] = true;

while (!Open.empty())
{
    const int Current = Open.front();
    Open.pop();

    for (int Next : Graph[Current])
    {
        if (!Visited[Next])
        {
            Visited[Next] = true;
            Open.push(Next);
        }
    }
}

모든 간선 비용이 같다면 BFS로 시작점에서 가장 적은 간선 수의 경로를 찾을 수 있다.

DFS

Depth-First Search는 한 경로를 끝까지 내려간 뒤 돌아온다. 재귀 호출이나 Stack을 사용한다.

void DFS(int Current)
{
    Visited[Current] = true;

    for (int Next : Graph[Current])
    {
        if (!Visited[Next])
        {
            DFS(Next);
        }
    }
}

연결 요소, 사이클 탐지, 백트래킹 구조에 자주 사용한다. 그래프가 매우 깊으면 재귀 Stack이 넘칠 수 있으므로 명시적인 Stack 구현을 고려한다.

BFS가 무조건 좋거나 DFS가 무조건 빠른 것은 아니다. 가까운 답이 필요한지, 경로를 깊게 시험해야 하는지, 메모리와 그래프 깊이가 어떤지에 따라 선택한다.