자바스크립트에서의 BFS와 DFS

    1. BFS (Breadth-First Search)

    BFS는 시작 노드에서부터 가까운 노드부터 차례로 방문하는 알고리즘입니다.
    보통 큐(Queue, FIFO: First-In, First-Out)를 사용합니다.
    최단 경로, 레벨 순회 등에 유용합니다.

    function bfsWithVisited(start, getNeighbors) {
        const queue = [start];
        const visited = new Set();
        visited.add(start);
        console.log("초기 visited:", Array.from(visited));
    
        while (queue.length > 0) {
            const current = queue.shift(); // 큐에서 가장 앞의 원소를 꺼냄
            console.log("현재 처리 노드:", current);
            // 현재 노드의 이웃들을 순회
            for (const neighbor of getNeighbors(current)) {
              if (!visited.has(neighbor)) {
                visited.add(neighbor);
                queue.push(neighbor);
                console.log(`새롭게 방문: ${neighbor} -> visited:`, Array.from(visited));
              }
            }
        }
        return visited;
    }
    
    // 예제 그래프 (인접 리스트 형태)
    const graph = {
    A: ['B', 'C'],
    B: ['A', 'D', 'E'],
    C: ['A', 'F'],
    D: ['B'],
    E: ['B', 'F'],
    F: ['C', 'E']
    };
    
    // BFS 실행 예시
    console.log("BFS 방문 결과:");
    bfsWithVisited('A', node => graph[node]);
    // 예상 BFS 방문 순서: A → B → C → D → E → F

     

     

    초기 상태에서 시작 노드 A를 큐와 visited에 추가합니다.
    큐에서 하나씩 꺼내며, 해당 노드의 이웃 중 아직 방문하지 않은 노드를 큐에 추가합니다.
    방문 상태(visited)는 Set으로 관리하여 중복 방문을 막습니다.

     


    2. DFS (Depth-First Search)

    DFS는 한 경로를 가능한 깊게 탐색한 후, 더 이상 진행할 수 없으면 백트래킹하여 다른 경로를 탐색합니다.
    재귀나 스택(Stack, LIFO: Last-In, First-Out)을 사용하여 구현할 수 있습니다.
    경로 탐색, 백트래킹, 사이클 감지 등에 유용합니다.


    2.1. 재귀 기반 DFS : 함수 호출 스택을 사용해 깊이 우선 탐색을 자연스럽게 구현합니다.

    function dfsRecursiveWithVisited(node, getNeighbors, visited = new Set()) {
        visited.add(node);
        console.log("현재 방문 노드:", node, "-> visited:", Array.from(visited));
    
        for (const neighbor of getNeighbors(node)) {
            if (!visited.has(neighbor)) {
            	dfsRecursiveWithVisited(neighbor, getNeighbors, visited);
            }
        }
        return visited;
    }
    
    // DFS 실행 예시 (재귀 방식)
    console.log("DFS (재귀) 방문 결과:");
    dfsRecursiveWithVisited('A', node => graph[node]);
    // 예상 DFS 방문 순서 (예시): A → B → D → E → F → C
    // (탐색 순서는 getNeighbors 함수의 반환 순서에 따라 달라질 수 있음)

     

    2.2. 스택 기반 DFS: 명시적인 스택을 사용하여 후입선출(LIFO) 방식으로, 마지막에 추가된 노드부터 처리합니다.

    function dfsStack(start, getNeighbors) {
        const stack = [start];
        const visited = new Set();
    
        while (stack.length > 0) {
        const current = stack.pop(); // 스택에서 마지막 요소를 꺼냄 (LIFO)
        if (!visited.has(current)) {
            visited.add(current);
            console.log("현재 방문 노드:", current, "-> visited:", Array.from(visited));
            // 이웃들을 스택에 추가 (순서는 이웃 배열 순서에 따라 다를 수 있음)
              for (const neighbor of getNeighbors(current)) {
                if (!visited.has(neighbor)) {
                  stack.push(neighbor);
                }
              }
            }
        }
        return visited;
    }
    
    // DFS 실행 예시 (스택 방식)
    console.log("DFS (스택) 방문 결과:");
    dfsStack('A', node => graph[node]);
    // 예상 DFS 방문 순서 (예시): A → C → F → E → B → D
    // (탐색 순서는 이웃의 추가 순서에 따라 달라질 수 있음)

     

     

    반응형

    댓글