JavaScript DFS(깊이 우선 탐색) BFS(너비 우선 탐색)

DFS 깊이 우선 탐색

최대한 깊이 내려간뒤, 마지막 노드를 찍고 옆으로 이동

개념 : 루트 노드에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색
장점 : BFS에 비해 좀 더 간단함
단점 : 탐색 속도가 느림
구현 : 스택 또는 재귀함수로 구현

//스택 사용

function dfs(graph, start) {
    let visited = Array(graph.length).fill(false); // 방문 여부를 저장할 배열
    let stack = [start]; // 탐색을 위한 스택
    let result = []; // 방문한 노드 순서를 기록

    while (stack.length > 0) {
        let node = stack.pop(); // 스택에서 가장 위의 노드 꺼냄

        if (!visited[node]) {
            visited[node] = true; // 방문 처리
            result.push(node); // 방문한 노드 저장
            console.log(node); // 방문한 노드 출력 (필요시 생략 가능)

            // 현재 노드와 연결된 노드들을 스택에 추가
            // 스택 특성상 역순으로 추가해야 탐색 순서가 제대로 됨
            for (let neighbor of graph[node].reverse()) {
                if (!visited[neighbor]) {
                    stack.push(neighbor);
                }
            }
        }
    }

    return result; // 탐색 순서를 반환
}

// 그래프 정의 (인접 리스트)
const graph = [
    [],          // 노드 0 (사용하지 않음)
    [2, 3, 4],   // 노드 1과 연결된 노드들
    [1, 5],      // 노드 2와 연결된 노드들
    [1],         // 노드 3과 연결된 노드들
    [1, 5],      // 노드 4와 연결된 노드들
    [2, 4]       // 노드 5와 연결된 노드들
];

// DFS 시작
console.log(dfs(graph, 1)); // 1번 노드부터 DFS 시작

//재귀함수 사용

function dfs(graph, visited, node) { 
    // 현재 노드를 방문 처리
    visited[node] = true;
    console.log(node); // 방문한 노드를 출력 (필요에 따라 다른 작업 수행 가능)

    // 현재 노드에 연결된 노드들을 탐색
    for (let neighbor of graph[node]) {
        if (!visited[neighbor]) {
            dfs(graph, visited, neighbor); // 방문하지 않은 노드로 재귀 호출
        }
    }
}

// 그래프 정의 (인접 리스트)
const graph = [
    [],          // 노드 0 (비워둠, 1번 노드부터 시작한다고 가정)
    [2, 3, 4],   // 노드 1과 연결된 노드들
    [1, 5],      // 노드 2와 연결된 노드들
    [1],         // 노드 3과 연결된 노드들
    [1, 5],      // 노드 4와 연결된 노드들
    [2, 4]       // 노드 5와 연결된 노드들
];

// 방문 배열 초기화
const visited = Array(graph.length).fill(false);

// DFS 시작
dfs(graph, visited, 1); // 1번 노드부터 시작

BFS 너비 우선 탐색

최대한 넒게 이동한뒤, 더 갈 노드가 없을 때 아래로 이동

개념 : 루트 노드에서 시작해서 인접한 노드를 먼저 탐색하는 방법
장점 : 두 노드 사이의 최단 경로를 찾고 싶을 때 이 방법 선택
구현 : 큐를 이용해서 구현

function bfsWithCustomQueue(graph, start) {
    let visited = Array(graph.length).fill(false);
    let queue = new Queue();
    let result = [];

    queue.enqueue(start);
    visited[start] = true;

    while (!queue.isEmpty()) {
        let node = queue.dequeue();
        result.push(node);

        for (let neighbor of graph[node]) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                queue.enqueue(neighbor);
            }
        }
    }

    return result;
}