[JS] 자료구조(3) 그래프 순회 BFS & DFS

그래프 순회

그래프를 순회 하는 방법은 다양하다. 가장 일반적인 방법으로 너비 우선 탐색과 깊이 우선 탐색이 있다.

너비 우선 탐색(BFS, Breadth-first search)

너비 우선 탐색은 그래프에서 연결된 노드와 해당 노드들 간의 간선을 순서대로 검색하는 알고리즘을 말한다. BFS는 방문한 노드들을 차례로 저장한 후 꺼낼 ㄱ수 있는 자료 구조인 큐를 사용한다. 즉 선입선출 원칙으로 탐색한다.

DirectedGraph.prototype.traverseBFS = function(vertex, fn) {
    var queue = [],
        visited = {};

    queue.push(vertex);

    while (queue.length) {
        vertex = queue.shift();
        if (!visited[vertex]) {
            visited[vertex] = true;
            fn(vertex);
            for (var adjacentVertex in this.edges[vertex]) {
                queue.push(adjacentVertex);
            }
        }
    }
}
digraph1.traverseBFS("B", (vertex) => {
    console.log(vertex)
});

깊이 우선 탐색(DFS, Depth-first search)

깊이 우선 탐색은 그래프에서 다른 연결을 방문하기 전에 하나의 연결을 깊게 파고들며 순회하는 검색 알고리즘을 말한다.

DirectedGraph.prototype.traverseDFS = function(vertex, fn) {
    var visited = {};
    this._traverseDFS(vertex, visited, fn);
}

DirectedGraph.prototype._traverseDFS = function(vertex, visited, fn) {
    visited[vertex] = true;
    fn(vertex);
    for (var adjacentVertex in this.edges[vertex]) {
        if (!visited[adjacentVertex]) {
            this._traverseDFS(adjacentVertex, visited, fn);
        }
    }
}

BFS와 DFS 모두 조건 내의 모든 노드를 검색한다는 점에서 시간 복잡도는 동일하지만 활용법이 다르다. **경로의 특징을 저장해야 하는 문제(예를 들면 각 정점에 숫자가 적혀있고 a부터 b까지 가는 경로를 구하는데 경로에 같은 숫자가 있으면 안 된다는 문제 등)는 DFS를, 최단거리를 구해야 하는 문제는 BFS가 유리하다. **