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

깊이우선탐색

깊이우선탐색은 가장 친숙한 그래프 탐색 방법 중 하나이다.

말 그대롭니다...
그래프의 깊이를 우선적으로 탐색하는 방식입니다.

깊이우선탐색은 두 가지 방법이 있다.
1. 스택(stack) 자료구조 사용
2. 재귀호출

대부분 재귀호출을 이용한 코드가 더 간단하고 사용하기 쉬워
재귀호출로 알고리즘을 구현한다.

먼저, 깊이우선탐색할 그래프를 통해서 탐색 순서를 봐보자.

진한 보라색의 노드부터 깊이우선탐색을 할 때의 순서를 각 노드에 적어보았다.

루트노드에서부터 아래방향으로 탐색을 한다.
그래프의 깊이(level)를 점점 높여가며 탐색한다.

그래프를 어떻게 저장하느냐에 따라서도 알고리즘이 바뀔 수 있다.
나는 일반적인 연결리스트로 그래프를 구현하여 탐색 알고리즘을 만들었다.

> 추가적인 알고리즘 관련 정보는 아래 링크를 통해 확인하길 바란다.

https://joooing.tistory.com/entry/DFS%EA%B9%8A%EC%9D%B4%EC%9A%B0%EC%84%A0%ED%83%90%EC%83%89-BFS%EB%84%88%EB%B9%84%EC%9A%B0%EC%84%A0%ED%83%90%EC%83%89
[참고자료]

 

자바구현코드

public static void Dfs(int n) {
	visited[n] = true;
		
	for(int i = 0;i<graph[n].size();i++) {
		int v = graph[n].get(i);
		if(!visited[v]) {
			count++;
			Dfs(v);
		}
	}
}

 - 나는 대부분 static 함수형태로 class 안에 넣어 main 함수에서 처음으로 탐색할 노드를 n으로 넣어 호출하는 방식으로 사용한다

 

구현된 함수 코드 사용 예시 - 백준 2606번

import java.util.*;

public class Baekjoon2606 {
	static boolean[] visited;
	static LinkedList<Integer> graph[];
	static int count;
	
	public static void Dfs(int n) {
		visited[n] = true;
		
		for(int i = 0;i<graph[n].size();i++) {
			int v = graph[n].get(i);
			if(!visited[v]) {
				count++;
				Dfs(v);
			}
		}
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int node = sc.nextInt();
		int edge = sc.nextInt();
		
		visited = new boolean[node + 1];
		graph = new LinkedList[node + 1];
		for(int i = 0;i<node + 1;i++) {
			graph[i] = new LinkedList<Integer>();
		}
		
		for(int i =0;i<edge;i++) {
			int r = sc.nextInt();
			int c = sc.nextInt();
			graph[r].add(c);
			graph[c].add(r);
		}
		
		Dfs(1);
		System.out.println(count);
	}
	
}

 

스택(stack)을 이용하여 구현된 자바 코드 및 설명은 아래 참고자료를 보기 바란다.

https://velog.io/@falling_star3/2.-%EA%B9%8A%EC%9D%B4%EC%9A%B0%EC%84%A0%ED%83%90%EC%83%89DFS%EA%B3%BC-%EB%84%93%EC%9D%B4%EC%9A%B0%EC%84%A0%ED%83%90%EC%83%89BFS
[Stack으로 구현된 DFS 참고자료]