자바스크립트에서의 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
// (탐색 순서는 이웃의 추가 순서에 따라 달라질 수 있음)