[알고리즘] 깊이 우선 탐색 (depth-first search) : DFS

DFS(depth-first search)란?

 

depth-first search

그래프 이론에서 많이 사용되는 탐색 알고리즘 중 하나다.

현재 정점에서 인접한 간선들을 하나씩 점검하다 아직 방문하지 않은 정점으로 향하는 간선이 있다면 그 간선을 무조건 따라가는 탐색 알고리즘이다.

이전까지 거쳐온 정점을 기억하기 위해서 재귀를 사용한다.

또한 그래프의 모든 정점이 간선을 통해 연결되어 있다는 보장이 없기 때문에 그래프의 전체 구조를 파악하기 위해서 

 

DFS로 풀 수 있는 유명한 문제를 살펴보겠습니다.

 

위상 정렬(topological sort)

그래프의 순서를 정렬하기 위한 방법이다.

각 정점의 의존 관계를 간선으로 표현한 의존성 그래프(dependency graph)의 순서를 나타내기 위해 사용된다.

이 그래프의 가장 큰 특징은 사이클이 없다는 점이다.

따라서 의존성 그래프는 사이클이 없는 방향 그래프 DAG다. 

 

위상 정렬을 구현하는 방법

topologicalSort

배열, 리스트, 큐를 이용해 구현한다.

다음과 같은 변수를 지정한다.

int indegree[]	들어오는 차수를 기록하는 배열
ArrayList<Integer>[] al	그래프에 연결된 간선를 기록하는 배열

 

n개의 정점이 존재하고 v1 -> v2라는 방향 그래프에 대한 m개의 입력이 들어오면 다음과 같이 입력을 초기화한다.

for(int i = 0; i < n+1; i++) {
			al[i] = new ArrayList<Integer>();
}

for(int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine());
			int v1 = Integer.parseInt(st.nextToken());
			int v2 = Integer.parseInt(st.nextToken());
			
			al[v1].add(v2);
			indegree[v2]++;
}

들어오는 차수가 0인 것을 큐에 넣고 해당 indegree의 값을 1씩 빼주면서 단계를 진행한다.

static void topologicalSort() {
		Queue<Integer> q = new LinkedList<>();

		for(int i = 1; i < indegree.length; i++) {
			if(indegree[i] == 0) {
				q.offer(i);
			}
		}
		
		while(!q.isEmpty()){
			int node = q.poll();
			result.add(node);

			for(Integer i : al[node]) {
				indegree[i]--;
				
				if(indegree[i] == 0) {
					q.offer(i);
				}
			}
		}
		
		return;
}