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

DFS는 그래프를 탐색하는 방식 중에 하나이다. 

깊이 우선 탐색( - 優先探索, 영어: depth-first search, DFS)은 맹목적 탐색방법의 하나로 탐색트리의 최근에 첨가된 노드를 선택하고, 이 노드에 적용 가능한 동작자 중 하나를 적용하여 트리에 다음 수준(level)의 한 개의 자식노드를 첨가하며, 첨가된 자식 노드가 목표노드일 때까지 앞의 자식 노드의 첨가 과정을 반복해 가는 방식이다.

1. 그래프

노드(node)와 그 노드를 연결하는 간선(edge)을 하나로 모아 놓은 비선형 자료 구조

그래프 : G = (V,E) 이고, V,E는 다음과 같다.

V(G) : 정점(set of vertices)

E(G) : 간선(set of edges), 정점을 연결하는 선, V X V의 부분집합

 

• 그래프는 node(혹은 vertice)와 edge(혹은 arcs)로 구성되어 있으며 연결되어 있는 객체 간의 관계를 표현할 수 있는 자료구조로 네트워크 모델이다.
• 간선이 방향을 갖는지 여부에 따라 무방향 그래프와 방향 그래프로 구분한다.
• 인접 리스트/인접 행렬 두 가지 방식으로 그래프를 구현할 수 있다.

2. 그래프 탐색

- 그래프의 각 정점을 방문하는 것을 탐색(traversal)이라고 한다.

- 그래프에 관한 연산 중 가장 중요한 것이다.

- 탐색에서 노드의 방문 순서에 따라 다음과 같은 방법이 있다.

 

• 깊이우선탐색 – DFS (Depth First Search) – 갈수있는데 까지 가보는 방문 방법 -트리의 전위탐색 방법을 그래프에 적용한 것이다. (preorder tree traversal)

• 너비우선탐색 – BFS (Breath First Search) – 거리가 가까운 곳부터 가보는 방문 방법 - 트리의 레벨우선탐색을 그래프에 적용한 것이다. (level order tree traversal)

 

3. 깊이 우선 탐색

방법 : 자동차로 여행할 경우 방문지가 있으면 무조건 방문하는 방법이다. 즉 후진하지 않고 가는 방법이며 후진하는 경우는 길이 막히거나, 이미 방문했던 곳일 경우이다. 후진하여 방문할 곳은 마지막에 갈수 있었던 곳 중 가지 않았던 길이다. 이 방법을 깊이 우선 탐색이라고 하며 탐색 중 방문 가능한 곳은 스택 자료를 이용하여 저장해 둔다.

 

1단계 : 하나의 노드를 택한다.

2단계 : 노드를 방문하여 필요한 작업을 한 다음 연결된 다음 노드를 찾는다. 현재 방문 노드는 스택에 저장한다. 2단계를 반복하면서 방문을 계속한다. 막히면 3단계로 간다.

3단계 : 더 이상 방문할 노드가 없으면 스택에서 노드를 빼내 다음 방문 노드를 찾아 2)번 과정을 다시 반복한다.

 

-깊이 우선 탐색 알고리즘

/* 정점 v에서 시작하여 그래프의 깊이 우선 방문 */
void dfs(int v) {
		node_ptr w;
		visited[v] = TRUE; /* 1 방문지 표시 */
		printf(“%5d”, v);
		for(w = graph[v]; w; w = w->link) /* 2 연결리스트 탐색 */
			if(!visited[w->vertex])
				dfs(w->vertex);
}

 

 

4. 깊이 우선 탐색의 시간 복잡도

 

- DFS는 그래프(정점의 수 : N, 간선의 수: E)의 모든 간선을 조회함

* 인접 리스트로 표현된 그래프 : O(N+E)

* 인접 행렬로 표현된 그래프 : O(N^2)