너비 우선 탐색과 깊이 우선 탐색 with JS(BFS, DFS)

너비 우선 탐색(BFS)과 깊이 우선 탐색(DFS): 그래프 탐색 알고리즘 이해하기

---

그래프 탐색은 복잡한 네트워크에서 특정 노드를 찾거나 경로를 분석할 때 사용하는 핵심 알고리즘입니다. 너비 우선 탐색(BFS)과 깊이 우선 탐색(DFS)는 이러한 탐색을 수행하는 두 가지 기본적인 방법입니다. 이 글에서는 각 알고리즘의 원리와 특징을 상세히 살펴보겠습니다.

---

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

BFS는 그래프의 모든 노드를 체계적으로 탐색하는 방법 중 하나입니다. 이 방법은 '가장 가까운 노드'부터 차례대로 탐색하며, 다음과 같은 특징을 가집니다:

• 큐(Queue) 사용: BFS는 탐색을 위해 FIFO(First-In-First-Out) 원칙을 따르는 큐 자료구조를 사용합니다.
• 최단 경로: BFS는 시작 지점에서 각 노드까지의 최단 경로를 찾는 데 사용될 수 있습니다. 특히 가중치가 없는 그래프에서 효과적입니다.
• 시간 복잡도: BFS의 시간 복잡도는 O(V+E)입니다. 여기서 V는 정점의 수, E는 간선의 수를 나타냅니다.

---

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

DFS는 그래프의 깊은 부분을 우선적으로 탐색하는 알고리즘으로, 다음과 같은 특징을 가집니다:

• 스택(Stack) 사용: DFS는 스택 자료구조를 사용하거나, 재귀 호출을 통해 구현할 수 있습니다.
• 경로 탐색: DFS는 가능한 모든 경로를 탐색하며, 주로 복잡한 경로 문제나 퍼즐을 해결하는 데 유용합니다.
• 시간 복잡도: DFS 역시 BFS와 동일하게 O(V+E)의 시간 복잡도를 가집니다.

---

자바스크립트로 구현하는 BFS와 DFS

class Graph {
    constructor() {
        this.adjacencyList = {};
    }

    addVertex(vertex) {
        if (!this.adjacencyList[vertex]) this.adjacencyList[vertex] = [];
    }

    addEdge(v1, v2) {
        this.adjacencyList[v1].push(v2);
        this.adjacencyList[v2].push(v1);
    }

    bfs(start) {
        const queue = [start];
        const result = [];
        const visited = {};
        visited[start] = true;

        while (queue.length) {
            let currentVertex = queue.shift();
            result.push(currentVertex);

            this.adjacencyList[currentVertex].forEach(neighbor => {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    queue.push(neighbor);
                }
            });
        }

        return result;
    }

    dfs(start) {
        const result = [];
        const visited = {};
        const adjacencyList = this.adjacencyList;

        (function dfsHelper(vertex) {
            if (!vertex) return null;
            visited[vertex] = true;
            result.push(vertex);
            adjacencyList[vertex].forEach(neighbor => {
                if (!visited[neighbor]) {
                    return dfsHelper(neighbor);
                }
            });
        })(start);

        return result;
    }
}