[DFS] DFS

깊이 우선 탐색(depth-first search, DFS)은 그래프의 모든 정점을 발견하는 가장 단순하고 고전적인 방법. 가능한 한 그래프 안으로 '깊이' 들어가려고 시도하며, 막힌 정점에 도달하지 않는 한 뒤로 돌아가지 않는다.

구현 (Java)

public class Code28_1 {
	
	// 노드 개수 (임시 값)
	public static int N = 30;
	// 방문 여부
	public static boolean[] visited = new boolean[N];
	// 각 노드 별 인접한 노드들의 List (인접 List)
	public static List<Integer>[] adj = new List[N];

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		
		// List 배열에 ArrayList 할당
		for(int i=0; i<adj.length; i++){
			adj[i] = new ArrayList<Integer>();
		}
		
		dfsAll();

	}
	
	public static void dfs(int here){
		visited[here] = true;
		
		for(int i=0; i<adj[here].size(); ++i){
			int there = adj[here].get(i);
			// 아직 방문한 적 없다면 방문한다.
			if(!visited[there]){
				dfs(there);
			}
		}
		
	}
	
	public static void dfsAll(){
		// visited를 모두 false로 초기화한다.
		Arrays.fill(visited, false);
		// 모든 정점을 순회하면서, 아직 방문한 적 없으면 방문한다.
		for(int i=0; i<adj.length; ++i){
			if(!visited[i]){
				dfs(i);
			}
		}
	}

}

한 가지 유의할 점은 모든 정점에 대해 순서대로 dfs()를 호출하는 dfsAll() 함수의 존재이다. 그래프에서는 모든 정점들이 간선을 통해 연결되어 있다는 보장이 없기 때문에, dfs()만으로는 모든 정점을 순서대로 발견한다는 목적에 부합하지 않는다.

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

인접 리스트 사용 : dfs()는 한 정점마다 한 번씩 호출되므로, 정확히 |V|번 호출된다. dfs() 한 번의 수행 시간은 모든 인접 간선을 검사하는 for문에 지배되는데, 모든 정점에 대해 dfs()를 수행하고 나면 모든 간선을 정확히 한 번(방향 그래프의 경우) 혹은 두 번 (무향 그래프의 경우) 확인함을 알 수 있다. 따라서 깊이 우선 탐색의 시간 복잡도는 O(|V| + |E|)가 된다.

인접 행렬을 사용하는 겨웅에도 dfs() 호출 횟수는 그대로 |V|번이다. 하지만 dfs() 내부에서 다른 모든 정점을 순회하며 두 정점 사이에 간선이 있는가를 확인해야 하기 때문에 한 번의 실행에 O(|V|)의 시간이 든다. 따라서 O(|V^2|)

활용1 : 두 정점이 서로 연결되어 있는지 확인하기

활용2 : 연결된 부분집합의 개수 세기
무향 그래프가 간선으로 서로 연결되지 않은 몇 개의 조각으로 쪼개져 잇는 경우, 각 연결된 정점들의 부분집합을 컴포넌트(component) 혹은 요소라고 부른다. dfs()는 시작한 정점에서 갈 수 잇는 모든 정점들을 방문하기 때문에, dfsAll()에서 dfs() 호출 횟수를 센다.

활용3 : 위상정렬
위상 정렬은 깊이 우선 탐색으로 풀 수 있는 가장 유명한 문제들 중 하나. 위상 정렬은 의존성이 있는 작업들의 주어질 때, 이들을 어떤 순서로 수행해야 하는지 계산해 준다.

각 작업을 정점으로 표현하고, 작업 간의 의존 관계를 간선으로 표현한 방향 그래프를 의존성 그래프(dependency graph)라고 한다. 작업 v가 u에 의존한다면, 의존성 그래프는 간선(u, v)를 포함하게 된다.

의존성 그래프에서 가장 먼저 알 수 잇는 특성은 그래프에 사이클이 없다는 점... 따라서 이 그래프(위상정렬 그래프)는 사이클 없는 방향 그래프, DAG가 된다.

위상 정렬을 구현하는 가장 직관적인 방법은 들어오는 간선이 하나도 없는 정점들을 하나씩 찾아서 정렬 결과의 뒤에 붙이고, 그래프에서 이 정점을 지우는 과정을 반복하는 것.

깊이 우선 탐색을 이용하면 더 간단하게 문제를 해결할 수 있다. dfsAll()을 수행하며 dfs()가 종료할 때마다 현재 정점의 번호를 기록하는 것. dfsAll()이 종료한 뒤 기록된 순서를 뒤집으면 위상 정렬 결과를 얻을 수 있다. 따라서 dfs()가 늦게 종료한 정점일 수록 정렬 결과의 앞에 온다.

* 알고리즘 문제해결전략 2권