[Algorithm] BFS & DFS

그래프 탐색 방법

그래프 탐색 방법중 대표적인 것이 BFS_{breadth first search}와 DFS_{depth first sesarch}이다.

 

너비우선 탐색(BFS)

특징

BFS는 탐색을 할 때, 자식을 차례대로 방문한다. 즉, 그래프 노드의 순서대로 방문한다. 이 순서를 지키기 위해 visited와 toVisit이라는 두 Queue를 활용한다.

BFS는 완전 탐색을 하기 때문에, 트리 내에 해가 있다면 반드시 해를 찾을 수 있다. 또한 트리의 depth 차례대로 방문하는 특성때문에, 가중치가 모두 동일한 그래프에서 해를 찾는다면 그 해가 최적의 해라는 것을 보장한다.

따라서 이전 상태로 회귀하는 것은 필수가 아니다. 또한 DFS와는 달리, 방문해야 할 노드 목록과 방문한 노드 목록을 각 콜 스택이 공유해야 한다.

 

예시 코드

// 탐색 순서는 아래 두 개의 큐에 의해 결정된다
const visited = [];
const toVisit = [];

function bfs(someParams) {
    // 해당 노드를 방문한 것으로 처리한다
    const thisNode = toVisit.shift();
    visited.push(thisNode);

    // 탈출 조건에 따라 탈출한다
    if(someContition) return;

    // 해당 노드에서 해야 할 작업을 수행한다.

    // 방문해야 할 다음 노드들을 추가한다.
    // 물론 이미 방문한 노드는 필터링해야 한다.
    toVisit.push(someChildren);

    // 재귀 호출을 한다.
    // DFS와는 다르게, 순회하면서 호출할 필요가 없다.
    bfs(someArgs);
}

 

깊이우선 탐색(DFS)

특징

DFS는 탐색을 할 때, 제일 높은 우선순위를 가진 자식 노드를 방문한다. 보통은 이 순서를 지키기 위해 별도의 자료구조가 필요하지 않으며, 단순히 자식 노드들에 대해 순회 호출하면 된다. (특별한 경우가 아니라면, 제일 왼쪽 노드를 먼저 탐색한다.)

DFS는 완전 탐색을 하기 때문에, 트리 내에 해가 존재한다면 무조건 찾을 수 있다. 다만 그 해가 최적의 해라는 것을 보장하지는 않는다.

트리의 depth가 엄청난 경우 성능이 좋지 않으므로, 이를 개선한 LDS_{limeted depth search}가 있다.

자식 노드를 탐색 후 부모 노드를 탐색해야 하므로 이전 상태로의 회귀가 필수적이다. (따라서 각 실행 컨텍스트 사이에 값을 공유하는 것을 조심해야 한다.)

 

예시 코드

function dfs(tree, somePrams) {
    // 탈출 조건에 따라 탈출한다
    if(someCondition) return;
    
    // 해당 노드에서 해야 할 작업을 수행한다
    
    // 자식들을 순회하며 재귀 호출을 한다
    children.forEach((child) => {
        // 각 콜 스택 간 데이터가 공유되면 안되기 때문에,
        // 인자를 이용해 디커플링된 값을 전달한다.
        dfs(tree, someArgs);
        
        // 자식 노드에서 백 트래킹한 후 필요한 동작을 수행한다.
    });
}