[알고리즘] DFS

DFS는 깊이 우선 탐색이라고 부르며, 깊은 부분부터 우선적으로 탐색하는 알고리즘이다.
DFS는 Stack 자료구조 혹은 재귀 함수를 이용하여 구현할 수 있다.

 

4 5 1
1 2
1 3
1 4
2 4
3 4

 

DFS로 위 예제를 탐색하게 되면 1 2 4 3 이라는 결과를 얻을 수 있다.
해당 노드에서 갈 수 있는 방향을 기준으로 가장 작은 노드를 선택해서 방문 처리하며 진행한다.
이를 반복하여 끝까지 도달한다.

 

구현

Static

private static void DFS_Stack(int start) {
    Stack <Integer> stack = new Stack();
    stack.add(start);

    while(!stack.isEmpty()) {
        int node = stack.pop();

        if (!visited[node]) {
            System.out.print(node + " ");
            visited[node] = true;
        }

        for (int next : adjList.get(node)) {
            if (visited[next]) continue;
            stack.add(next);
        }
    }
}

• 탐색 시작 노드를 스택에 삽입하고 아직 방문하지 않은 인접 노드를 탐색하여 스택에 추가한다.
• 스택 내 최상단 노드를 꺼내 아직 방문하지 않은 인접 노드가 있다면 해당 노드를 스택에 넣고 방문 처리를 한다.
• 인접한 노드가 하나도 없으면, 스택에서 최상단 노드를 꺼낸다.
• 2, 3번 과정을 반복한다.

 

Recursion

private static void DFS_Recursion(int v) {
    if (!visited[v]) {
        System.out.print(v + " ");
        visited[v] = true;
    }

    for (int i = 0; i < adjList.get(v).size(); i++) {
        if (visited[adjList.get(v).get(i)]) continue;
        DFS_Recursion(adjList.get(v).get(i));
    }
}

• 탐색 시작 노드를 메서드의 파라미터에 삽입하고 방문처리를 한다.
• 아직 방문하지 않은 인접 노드가 있다면 해당 노드를 스택프레임에 넣고 방문 처리를 한다.
• 인접한 노드가 하나도 없으면, 스택프레임에서 최상단 노드를 꺼낸다.
• 2, 3번 과정을 반복한다.