[알고리즘] 깊이 우선 탐색 (Depth First Search, DFS) - JAVA/자바

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

  : 하나의 정점으로부터 시작하여 깊은 곳 우선으로 탐색하여 최종적으로 연결된 모든 정점을 탐색하는 방법

 

특징

  ① 경로상의 노드들만 기억하면 되므로 차지하는 저장 공간이 적다.

  ② 같은 레벨의 경로보다 더 깊은 레벨을 우선으로 탐색한다.

  ③ 재귀적으로 동작하며, 후입 선출(LIFO, Last In First Out) 구조이다.

---

알고리즘

① 시작 정점 v를 결정하여 방문
② 정점 v에 인접한 정점 중
    1. 방문하지 않은 정점 w가 있으면, 정점 v를 스택에 push 하고 w를 방문하고 w를 v에 대입하여 ②과정 반복 수행
    2. 방문하지 않은 정점이 없으면, 탐색의 방향을 바꾸기 위해 마지막 방문 정점을 스택을 pop 하여 받은 정점 v로 하여 다시 ②과정 반복 수행
③ 스택이 공백이 될 때까지 ②반복 수행

답 >>>

A - B - D - G - E - C - F

---

의사 코드(Pseudo code)

DFS(v)
    for (i ← 0; i<n; i ← i+1) do {
        visited[i] ← false;
    }
    stack ← createStack();
    visited[v] ← true;
    while (not isEmpty(stack)) do {
        if (visited[v의 인접정점 w] = false) then {
            push(stack, v);
            visited[w] ← true;
            w 방문;
            v ← w;
        }
        else v ← pop(stack);
    }
end DFS()

---

DFS의 특성상 알고리즘은 두 가지 방법으로 구현할 수 있다.

  1. 재귀 호출 (Recursion)

  2. 스택 (Stack)

---

Java 코드 구현

1. 재귀 호출

static Stack<Integer> stack = new Stack<>();
static StringBuilder sb = new StringBuilder();
static boolean node[][] = new boolean[n+1][n+1], visited[] = new boolean[n+1];
static void dfs(int v) {
	if(visited[v])
    	return;
	sb.append(v+" ");
	for(int i=1; i<=n; i++)
		if(node[v][i] && !visited[i]) {
			visited[i] = true;
			dfs(i);
		}
}

2. 스택 사용

public static String dfs(int v, boolean node[][]) {
    StringBuilder sb = new StringBuilder();
    Stack<Integer> stack = new Stack<>();
    boolean visited[] = new boolean[n+1];
    stack.add(v);
    int idx;
    while(!stack.isEmpty()) {
        idx = stack.pop();
        if(visited[idx])
            continue;
        visited[idx] = true;
        sb.append(idx+" ");
        for(int i=0; i<n; i++)
            if(node[idx][i] && !visited[i])
                stack.add(i);
    }
    return sb.toString();
}

시간 복잡도

 - 인접 리스트 = O(N+E)

 - 인접 행렬 = O(N^2)

* N = 정점의 수, E = 간선(노드)의 수

---

대표적인 DFS 사용 예

 - 전위 순회(표기법)

 - 미로 탐색

 - 그래프 사이클 찾기

 - 그래프 연결 요소 찾기

 - 그 외....