DFS(깊이우선순회)

이 글은 인프런의 영리한 프로그래밍을 위한 알고리즘 강의를 듣고 정리한 내용입니다.

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

맹목적 탐색방법의 하나로 탐색트리의 최근에 첨가된 노드를 선택하고, 이 노드에 적용 가능한 동작자 중 하나를 적용하여 트리에 다음 수준(Level)의 한 개의 자식노드를 첨가하여, 첨가된 자식 노드가 목표노드일 때까지 앞의 자식노드의 첨가 과정을 반복해가는 방식이다.

장점 : 

- 단지 한 경로상의 노드들만을 기억하면 되므로 저장공간의 수요가 비교적 적다.

- 목표노드가 깊은 단계가 있을 경우 해를 빨리 구할 수 있다.

단점 : 

- 해가 없는 경로에 깊이 빠질 가능성이 있다. 

- 따라서 실제의 경우 미리 지정한 임의의 깊이까지만 탐색하고 목표노드를 발견하지 못하면 다음의 경로를 따라 탐색하는 방법이 유용하다.

- 얻어진 해가 최단 경로가 된다는 보장이 없다.

- 목표에 이르는 경로가 다수인 문제에 대해 깊이 우선 탐색은 해에 다다르면 탐색을 끝내버리므로, 이때 얻어진 해는 최적이 아닐수도 있다는 말이다.

DFS(깊이우선탐색) 의사코드

DFS(G, v){
	visited[v] <- YES;
	for each node u adjacent to v do
		if visited[u] = no then
			DFS(G, u);
		end.
	end.
}

- 그래프가 disconnected이거나 혹은 방향그래프라면 DFS에 의해서 모든 노드가 방문되지 않을 수도 있음

- DFS를 반복하여 모든 노드 방문

DFS-ALL(G){
	for each v∈V
		visited[v] <- NO;
	for each v∈V
		if(visited[v]=NO) then
			DFS(G, v);
}

시간복잡도

인접 리스트 -> O(n+m)

인접 행렬 -> O(n^2)

소스 코드(Java)