깊이 우선 탐색(DFS)

• Depth First Search

• 특정 정점(노드)에서 시작해서 트리나 그래프에서 한 가지 경로를 최대한 깊게 탐색하고, 해당 경로를 끝까지 탐색한 후 다른 경로로 이동

• 미로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가, 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 다른 방향으로 다시 탐색을 진행하는 방법과 유사

• 모든 정점을 방문하고자 하는 경우에 사용

DFS의 특징

• 일반적으로 재귀 함수를 사용하여 구현(스택으로도 구현 가능)

• 모든 경우의 수에 대해 탐색을 진행

• 사이클이 있는 경우, 무한 루프에 빠지지 않도록 방문 체크 해주어야 함

• 사이클(Cycle): 그래프에서 한 노드에서 시작해, 여러 간선을 지나 시작 노드로 다시 도착하는 경로

• BFS보다 깊은 경로를 빠르게 찾는데 용이

DFS의 진행 순서

한 방향으로 갈 수 있을 때까지 계속 가다가, 더 이상 갈 수 없게 되면 다시 가장 가까운 분기점으로 돌아와서 다른 방향으로 다시 탐색을 진행

DFS의 구현

def dfs(now):
	visited[now] = 1 # 현재 노드를 방문한 것으로 표시
    print(now, end=" ") # 현재 노드를 출력
    
    for next in v[now]: # 모든 이웃 노드 'next'에 대해서 반복
    	if visited[next] == 0: # 만약 'next'를 아직 방문하지 않았다면
        	dfs(next)

static void dfs(int now) {
	visited[now] = 1;
    System.out.print(now + " ");
    for (int next : v.get(now)) {
    	if (visited[next] == 0) {
        	dfs(next);
        }
    }
}

void dfs(int now) {
	visited[now] = 1;
    cout << now " ";
    for (int &next: v[now]) {
    	if (!visited[next]) {
        	dfs(next);
        }
    }
}

DFS의 시간 복잡도

• $V$ → 정점(노드)의 수, $E$ → 간선의 수

• 인접 리스트로 표현된 그래프: $O(V + E)$

• 인정 행렬로 표현된 그래프: $O(V^2)$

• 희소 그래프의 경우 인접 행렬보다 인접 리스트를 사용하는 것이 유리

• 희소 그래프(Sparse Graph): 그래프 내에 적은 숫자의 간선만을 가지는 그래프

인접 리스트로 표현된 그래프: $O(V + E)$

행렬로 표현된 그래프: $O(V^2)$