[알고리즘] BFS(넓이 우선 탐색) & DFS(깊이 우선 탐색) - javascript

들어가기 전에...

해당 글은 유데미 JavaScript 알고리즘 & 자료구조 마스터클래스 강의를 바탕으로 작성되었다.

📌 BFS (넓이 우선 탐색)

이진 트리

// 노드 형식
class Node {
    constructor(val) {
        this.value = val;
        this.left = null;
        this.right = null;
    }
}

BFS(rootNode) {
    if(!rootNode) return null;

    let queue = [rootNode];
    let visited = [];
    let current;

    while(queue.length) {
        current = queue.shift();
        visited.push(current.value);
        if(current.left) queue.push(current.left);
        if(current.right) queue.push(current.right);
    }

    return visited;
}

그래프

// 그래프 예시
const graph = {
    "A": ["B", "C"],
    "B": ["A", "D"],
    "C": ["A", "E"],
    "D": ["B", "E", "F"],
    "E": ["C", "D", "F"],
    "F": ["D", "E"]
}

function bfs(graph, startNode) {
    let result = [];
    let queue = [startNode];
    let visited = {[startNode]: true};
    let curVertex;

    while(queue.length) {
        curVertex = queue.shift();
        result.push(curVertex);
        graph[curVertex].forEach(neighbor => {
            if(!visited[neighbor]) {
                visited[neighbor] = true;
                queue.push(neighbor);
            }
        })
    }

    return result;
}

📌 DFS (깊이 우선 탐색)

이진 트리

// 전위순회: 노드 -> 왼 -> 오
DFSPreOrder() {
    let result = [];

    function traverse(node) {
        result.push(node.value);
        if(node.left) traverse(node.left);
        if(node.right) traverse(node.right);
    }

    traverse(this.root);
    return result;
}

// 후위순회: 왼 -> 오 -> 노드
DFSPostOreder() {
    let result = [];

    function traverse(node) {
        if(node.left) traverse(node.left);
        if(node.right) traverse(node.right);
        result.push(node.value);
    }

    traverse(this.root);
    return result;
}

// 중위순회: 왼쪽 먼저 -> 노드 -> 오
DFSInOrder() {
    let result = [];

    function traverse(node) {
        if(node.left) traverse(node.left);
        result.push(node.value);
        if(node.right) traverse(node.right);
    }

    traverse(this.root);
    return result;
}

그래프

// 1️⃣재귀적 용법
function depthFirstSearch(graph, startNode) {
    let result = [];
    let visited = {}; // 방문시 "A": true 같이 기록

    (function dfs(vertex) {
        if(!vertex) return; // 노드값이 올바르지 않을시 처리
        result.push(vertex); // 결과값에 추가
        visited[vertex] = true; // 방문 처리
        graph[vertex].forEach(neighbor => { // 방문하지 않은 이웃 순회
            if(!visited[neighbor]) dfs(neighbor);
        })
    })(startNode);

    return result;
}

// 2️⃣반복적 용법
function dfs(graph, startNode) {
    let result = [];
    let stack = [startNode];
    let visited = {[startNode]: true};
    let curVertex;

    while(stack.length) {
        curVertex = stack.pop();
        result.push(curVertex);
        graph[curVertex].forEach(neighbor => {
                if(!visited[neighbor]) {
                    visited[neighbor] = true; // 여기서 방문처리 했으니 이후 스택에 추가x
                    stack.push(neighbor);
            }
        })
    }

    return result;
}

🤔 어떤 방법이 더 좋을까?

BFS vs DFS

• 시간 복잡도: 노드를 하나씩 방문하는 것은 같으므로 동일함
• 공간 복잡도
  • BFS: 넓이가 넓을수록 큐에 저장되는 노드가 많아서 메모리 많이 차지
  • DFS: 깊이가 깊을수록 재귀함수가 많이 실행되므로 메모리를 많이 차지
    ∴넓이가 넓으면 DFS / 깊이가 깊으면 BFS

DFS의 중위 vs 전위

• 중위: 오름차순으로 순회 (맨 왼쪽 리프부터 저장됨) -> 순서대로 작업해야 하거나, 데이터로 저장될 경우 유리함
• 전위: 루트부터 왼, 오 차례로 저장됨 -> 트리를 복사하거나 평탄화해서 저장하는 경우 유리함