DFS & BFS

DFS (Depth-First Search, 깊이 우선 탐색)

특징 및 방법:

• 스택 또는 재귀 함수를 사용
• 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색
• 모든 노드를 방문, 경로의 특징을 저장
• 구현이 간단하나 BFS보다 느림

시간복잡도: O(V + E) (V는 노드 수, E는 간선 수)

function dfs(graph, start) {
    const visited = new Set();
    const stack = [start];

    while (stack.length) {
        const node = stack.pop();
        if (!visited.has(node)) {
            visited.add(node);
            console.log(node); 
            graph[node].forEach(neighbor => {
                if (!visited.has(neighbor)) {
                    stack.push(neighbor);
                }
            });
        }
    }
}

 

BFS (Breadth-First Search, 너비 우선 탐색)

특징 및 방법:

• 큐를 사용
• 시작 노드에서 가까운 노드부터 차례대로 방문하고, 각 노드의 인접 노드를 큐에 추가
• 두 노드 사이의 최단 경로 구할 때 사용

시간복잡도: O(V + E)

function bfs(graph, start) {
    const visited = new Set();
    const queue = [start];

    while (queue.length) {
        const node = queue.shift();
        if (!visited.has(node)) {
            visited.add(node);
            console.log(node); // 노드 방문 처리
            graph[node].forEach(neighbor => {
                if (!visited.has(neighbor)) {
                    queue.push(neighbor);
                }
            });
        }
    }
}