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

그래프의 모든 정점들을 방문하는 방법은 크게 두 가지가 있다. 이번에 배워볼 알고리즘은 그중 하나인 깊이 우선 탐색(Depth First Search)이다. 줄여서 흔히 DFS라고 부른다. 이 알고리즘은 깊이 우선 탐색이란 말 그대로 깊이(Depth)를 우선순위로 두고 탐색을 하겠다는 의미이다.

​깊이 우선 탐색은 스택(Stack)을 이용해서 구현한다. 또한, 컴퓨터는 구조적으로 함수를 호출할 때 스택의 원리를 이용하기 때문에 스택을 선언하여 사용하지 않고 재귀적 함수 호출로 구현할 수도 있다.

필자는 재귀적인 구현이 훨씬 간단하고 직관적이기 때문에 보통 재귀적으로 구현을 많이 하는 편이다. 다만, 과도한 재귀 함수 호출은 스택에 함수가 계속 쌓이게 되면서 메모리에 많은 부담을 주기 때문에 이런 경우는 스택 자료구조를 선언해서 구현하는 편이다.

​

깊이 우선 탐색의 원리는 다음과 같다.

• 스택 최상단의 노드를 확인한다.
• 최상단 노드에 인접한 노드들 중 아직 방문하지 않은 노드가 있다면 그 노드를 스택에 넣어주고 방문 표시를 해준다. 만약 인접한 노드들 모두가 방문하였다면 스택에서 최상단 노드를 빼준다.

​

이 과정을 스택에 노드가 없어질 때까지 반복해 주면 된다. 깊이 우선 탐색은 글보다 그림으로 이해하는 것이 쉽다. 예를 들어 다음 그림과 같은 그래프가 있다고 하자.

 

이 그래프에서 깊이 우선 탐색 방법으로 모든 노드를 탐색하는 과정을 살펴보자. 0번 노드에서 시작을 하고 방문 순서는 구현하기 나름이지만 자식 노드들 중 숫자가 낮은 노드를 먼저 탐색하도록 하겠다.

먼저 방문하는 0번 노드를 스택에 담아준다. 또한, 우리는 모든 노드를 한 번만 탐색할 것이기 때문에 중복 탐색을 방지하기 위해 방문했다는 표시를 해준다.

 

현재 최상단 노드인 0번 노드에 인접한 노드들 중 방문하지 않은 노드들은 1, 2, 3번 노드이다. 이중 숫자가 가장 낮은 1번 노드를 스택에 담아주고 방문 표시를 해준다.

 

현재 최상단 노드인 1번 노드에 인접한 노드들 중 방문하지 않은 노드들은 4, 5번 노드이다. 이중 숫자가 가장 낮은 4번 노드를 스택에 담아주고 방문 표시를 해준다.

 

현재 최상단 노드인 4번 노드에 인전합 노드들 중 방문하지 않은 노드가 없기 때문에 4번 노드를 스택에서 빼준다.

 

현재 최상단 노드인 1번 노드에 인접한 5번 노드가 아직 방문하지 않았기 때문에 스택에 담아주고 방문 표시를 해준다.

 

현재 최상단 노드인 5번 노드에 인전합 노드들 중 방문하지 않은 노드가 없기 때문에 스택에서 5번 노드를 빼준다. 또한, 1번 노드 역시 자식 노드들 중 방문하지 않은 노드가 없기 때문에 마찬가지로 스택에서 빼준다.

 

현재 최상단 노드인 0번 노드에 인접한 노드들 중 방문하지 않은 노드들은 2, 3번 노드이다. 이중 숫자가 낮은 2번 노드를 스택에 담아주고 방문 표시를 해준다.

 

현재 최상단 노드인 2번 노드에 인접한 노드들 중 방문하지 않은 6번 노드를 스택에 담아주고 방문 표시를 해준다.

 

현재 최상단 노드인 6번 노드에 인접한 노드들 중 방문하지 않은 노드들은 3, 7번 노드이다. 이중 숫자가 낮은 3번 노드를 스택에 담아주고 방문 표시를 해준다.

 

현재 최상단 노드인 3번 노드에 인접한 노드들 중 방문하지 않은 7번 노드를 스택에 담아주고 방문 표시를 해준다.

 

모든 노드들을 방문하였기 때문에 스택에 남아있는 노드들을 빼주고 탐색을 종료한다.

 

0번 노드를 기준으로 그래프를 탐색한 순서는 0 - 1 - 4 - 5 - 2 - 6 - 3 - 7이다. 어떻게 구현하기에 따라 방문순서가 조금 바뀔 수는 있지만, 원리는 똑같기에 그래프의 모든 노드를 방문하게 된다.

​

이전 그래프 자료구조를 공부할 때 그래프를 구현하는 방법은 인접 행렬, 인접 리스트 두 가지 방법이 있다고 하였다. 깊이 우선 탐색은 그래프의 모든 간선을 조사하므로 정점의 수가 n이고 간선의 수가 e인 그래프를 깊이 우선 탐색하는 시간은 그래프가 인접 행렬로 구현되었다면 O(n^2)의 시간 복잡도를 가지며, 인접 리스트로 구현되어 있다면 O(n+e)의 시간 복잡도를 가진다.

​

다음은 Java로 스택 선언 & 재귀적 방법으로 구현한 DFS 알고리즘이다.

import java.util.Arrays;
import java.util.Stack;

class MyGraph {
	int vertexCnt;
	int[][] m;
	boolean[] visit;
	
	public MyGraph(int N) {
		vertexCnt = N;
		m = new int[N][N];
		visit = new boolean[N];
	}

	public void init() {
		Arrays.fill(visit, false);
	}
	
	public void makeUndirectedEdge(int from, int to) {
		m[from][to] = 1;
		m[to][from] = 1;
	}

	public void dfsStack(int v) {
		Stack<Integer> st = new Stack<>();
		st.push(v);
		visit[v] = true;
		System.out.print(v + "  ");
		
		while (!st.isEmpty()) {
			int now = st.peek();
			boolean flag = false;
			
			for (int i = 0; i < vertexCnt; ++i) {
				if (m[now][i] == 1 && !visit[i]) {
					visit[i] = true;
					flag = true;
					st.push(i);
					System.out.print(i + "  ");
					break;
				}
			}
			
			if (!flag) {
				st.pop();
			}
		}
	}

	public void dfsRecursion(int v) {
		visit[v] = true;
		System.out.print(v + "  ");
		
		for (int i = 0; i < vertexCnt; ++i) {
			if (m[v][i] == 1 && !visit[i]) {
				visit[i] = true;
				dfsRecursion(i);
			}
		}
	}
}

public class Blog {

	public static void main(String[] args) {
		MyGraph mg = new MyGraph(8);
		mg.makeUndirectedEdge(0, 1);
		mg.makeUndirectedEdge(0, 2);
		mg.makeUndirectedEdge(0, 3);
		mg.makeUndirectedEdge(1, 4);
		mg.makeUndirectedEdge(1, 5);
		mg.makeUndirectedEdge(2, 6);
		mg.makeUndirectedEdge(3, 6);
		mg.makeUndirectedEdge(3, 7);
		mg.dfsStack(0);
		mg.init();
		mg.dfsRecursion(0);
	}
}