DFS

DFS

깊이 우선 탐색은 그래프 완전 탐색 기법 중 하나이다. 깊이 우선 탐색은 그래프의 시작 노드에서 출발하여 탐색할 쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동하여 다시 탐색을 수행하는 알고리즘이다.

깊이 우선 탐색을 응용하여 풀 수 있는 문제는 단절점 찾기, 단절선 찾기, 사이클 찾기, 위상 정렬 등이 있다.

 

DFS 핵심 이론

DFS는 한번 방문한 노드를 다시 방문하면 안 되므로 노드 방문 여부를 체크할 배열이 필요하며, 그래프는 인접 리스트로 표현한다.

1. DFS를 시작할 노드를 정한 후 사용할 자료구조 초기화

   DFS를 위해 필요한 초기 작업은 인접 리스트로 그래프 표현하기, 방문 배열 초기화하기, 시작 노드 스택에 삽입하기이다.

2. 스택에서 노드 꺼낸 후 꺼낸 노드의 인접 노드를 다시 스택에 삽입

   pop을 수행하여 노드를 꺼낸다.

   꺼낸 노드를 탐색 순서에 기입하고 인접 리스트의 인접 노드를 스택에 삽입하며 방문 배열을 체크한다.

3. 스택 자료구조에 값이 없을 때까지 반복

   앞의 과정을 스택 자료구조에 값이 없을 때까지 반복한다.

   이미 다녀간 노드는 방문 배열을 바탕으로 재삽입하지 않는다.

 

코드 예시

static boolean visit[] // 방문 배열 선언
static ArrayList<Integer>[] A // 인접 리스트 선언

public static void DFS(int Node) {  // DFS 구현하기
	visit[Node] = true;
    for(int i : A[Node]) {
    	if(!visited[i]) {
        	DFS(i);
        }
    }
}

 

시간 복잡도(노드 수 : V, 에지 수 : E)

 - 인접 리스트 = O(V+E)

 - 인접 행렬 = O(V^2)