[스터디/알고리즘] DFS

시작하며

이번 주 스터디에서 준비해서 발표할 알고리즘은 DFS이다. 어떤 알고리즘인지 알고 있지만 다시 공부한다 생각하고 정리해 본다.

DFS(Depth First Search)

DFS(Depth First Search, 깊이 우선 탐색) 는 그래프 탐색 방법 중 하나이다. 깊이 우선 탐색이라는 말 그대로 그래프에서 가장 깊은 부분을 우선적으로 탐색하는 알고리즘이다.

최대한 깊숙히 들어가면서 노드를 방문한 후, 다시 돌아가서 다른 경로를 탐색하는 것이 DFS의 동작 과정이며, 이를 위해 스택 자료구조를 이용한다. 자세한 과정은 다음과 같다.

1. 탐색을 시작하는 노드(시작점)을 스택에 삽입(push) 하고 방문 처리한다. (방문 처리를 하는 이유는 이미 탐색한 노드를 다시 스택에 삽입하지 않게 하기 위함이다.)
2. 스택의 가장 위 노드를 꺼내면서(pop), 그 노드에 방문하지 않은 인접 노드가 있다면 그 인접 노드를 스택에 젛고 방문 처리한다. 그러한 인접 노드가 없다면 다시 스택에서 가장 위 노드를 꺼낸다.
3. 이 과정을 모두 끝날 때 까지 반복한다.

위처럼 스택을 이용해서 구현할 수도 있고, 재귀함수(재귀함수의 호출도 스택 영역에서 이루어지며, 같은 과정을 가진다.)를 이용해서 구현할 수도 있다.

구현 예시

예를 들어, 아래와 같은 모양의 그래프가 있다.

위 그래프에서 DFS를 수행하는 코드와 결과는 다음과 같다. (그래프는 인접 리스트 형태로 재귀함수를 이용해 구현하였다.)

코드

package algorithm;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

public class GraphSearch {

  static void initGraph(HashMap<Integer, List<Integer>> graph) {
    for (int i=1; i<=8; i++) {
      graph.put(i, new ArrayList<>());
    }

    graph.get(1).add(2);
    graph.get(1).add(3);
    graph.get(1).add(4);

    graph.get(2).add(7);

    graph.get(4).add(5);
    graph.get(4).add(6);

    graph.get(5).add(6);

    graph.get(7).add(8);
  }

  static void DFS(int vertex, HashMap<Integer, List<Integer>> graph,
      boolean[] visited) {
    visited[vertex] = true;
    System.out.print(vertex + " ");

    for (int v: graph.get(vertex)) {
      if (!visited[v]) {
        DFS(v, graph, visited);
      }
    }
  }

  public static void main(String[] args) {
    HashMap<Integer, List<Integer>> graph = new HashMap<>();
    boolean[] visited = new boolean[9];

    initGraph(graph);
    DFS(1, graph, visited);
  }
}

결과

1 2 7 8 3 4 5 6