DFS (Depth First Search) 구현해보기

DFS

트리나 그래프 등에서 하나의 노드를 최대한 깊게 들어가면서 해를 찾는 탐색 기법

장점

인접한 후보 노드만 기억하면 되므로 적은 기억공간 소요, 노드가 싶은 단계에 있을 경우 빠르게 정답 산출

단점

선택한 경로가 답이 아닐 경우 불필요한 탐색 가능, 최단 경로(BFS)를 구할 시 찾은 해가 정답이 아닐 경우 발생

⇒ 단점을 극복한게 BFS라고 보면 되는데, 순열과 조합 같은 완전 탐색에 자주 사용된다.

구현 메서드

• 재귀를 이용한 탐색: Graph._dfsRecursiveVisit()
• 스택을 이용한 탐색: Graph._dfsLoopVisit()

1. addVertex(), add Edge(), print()메서드의 경우 Graph와 동일

방문했는지의 여부를 확인하기 위해서 visited 객체 추가

import { Stack } from "./stack.mjs";
class Graph {
    constructor () {
        this.edge = {};
        this.visited = {};
    }

    addVertex (v) {
        this.edge[v] = [];
        this.visited[v] = false;
    }

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

    print () {
        for (let vertex in this.edge) {
            let neighbors = this.edge[vertex];
            if (neighbors.length === 0) continue;

            process.stdout.write(`${vertex} -> `);

            for (let i = 0; i < neighbors.length; ++i) {
                process.stdout.write(`${neighbors[i]} `);
            }

            console.log("");
        }
    }
}

2. 재귀를 이용한 탐색 (_dfsRecursiveVisit())

1. 이미 vertex를 방문했을 때는 return 하고, 새로 시행되면 visited 상태를 true로 바꿔준다.
2. 해당 vertex와 연결되어 있는 vertex 모두를 재귀를 통해 탐색한다.

_dfsRecursiveVisit(vertex) {
        if (this.visited[vertex]) return;

        this.visited[vertex] = true;
        console.log(`visited ${vertex} `);

        let neighbors = this.edge[vertex];
        for (let i = 0; i < neighbors.length; ++i) {
            this._dfsRecursiveVisit(neighbors[i]);
        }
    }

3. 스택을 이용한 탐색 (_dfsLoopVisit())

1. 스택을 import해서 사용한다.
2. 우선 첫 vertex를 스택에 담은 다음, 스택의 길이가 0이 아닐 때 스택의 pop과 visited 상태를 true로 바꿔준다.
3. 해당 vertex와 연결되어 있는 vertex를 가장 뒤에서부터 스택에 담는다.
4. 스택의 길이가 0이 될 때까지 반복한다.

_dfsLoopVisit (vertex) {
        let stack = new Stack();
        stack.push(vertex);

        while (!stack.isEmpty()) {
            let vertex = stack.pop();
            if (this.visited[vertex]) continue;

            this.visited[vertex] = true;
            console.log(`visited ${vertex} `);
            
            let neighbors = this.edge[vertex];
            for (let i = neighbors.length - 1; i >= 0; --i) {
                stack.push(neighbors[i]);
            }
        }
}

관련 전체 코드는 Git에 업로드 해두었습니다.
Github_DFS Recursive
Github_DFS Stack