DFS (Depth First Search )

# 정의

너비우선탐색이라 불리는 DFS 알고리즘은 굉장히 잘 알려져있고 컴퓨터 관련 전공생들은 거의 모두 알고 있는 알고리즘이다. chatGPT에 따른 DFS의 정의는 다음과 같다.

DFS는 그래프의 한 노드에서 시작하여 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법입니다. 즉, 더 이상 탐색할 수 없을 때까지 깊이 우선으로 탐색합니다.

DFS를 이해하기 위해선 "그래프"라는 것이 무엇인지부터 알아야한다. BFS를 설명할때 이미 했기 때문에 링크만 올려두겠다.

https://whitem4rk.tistory.com/18

BFS (Breadth First Search )

 

# Code

이제 개념을 장착했으니 DFS가 어떤 방식으로 코드상에서 진행되는지 알아보자

1. 현재 노드에서 방문하지 않은 인접 노드를 하나씩 방문하며, 해당 노드가 방문되지 않은 경우에만 재귀 호출
2. 방문한 노드는 visited 집합에 추가되고, 노드를 출력
3. 이렇게 모든 인접 노드를 탐색한 뒤, 재귀 함수를 호출한 이전 노드로 돌아갑니다.
4. 이전 노드에서 방문하지 않은 다음 인접 노드를 찾아 방문하는 과정을 반복하여 그래프를 탐색

 

가장 기본적인 DFS 파이썬 코드이다.

def dfs_recursive(graph, start, visited):
    visited.add(start)
    print(start, end=' ')
    for next_node in graph[start]:
        if next_node not in visited:
            dfs_recursive(graph, next_node, visited)

 

# DFS 수행시간

1. 인접 리스트를 이용하여 그래프를 표현하는 경우, DFS 알고리즘의 수행시간은 O(V+E)입니다. 이는 모든 정점을 방문하고, 모든 간선을 한 번씩만 탐색하기 때문입니다.
2. 인접 행렬을 이용하여 그래프를 표현하는 경우, DFS 알고리즘의 수행시간은 O(V^2)입니다. 이는 모든 정점을 방문하고, 모든 정점 쌍에 대해 인접 여부를 확인하기 때문입니다.

인접 행렬은 간선의 개수가 적은 희소 그래프에서는 메모리 낭비가 심하고, 인접 리스트보다 실행 속도가 느리기 때문에 대부분의 경우 인접 리스트를 사용합니다.
그러나 DFS는 깊이 우선 탐색이기 때문에, 그래프의 구조에 따라 최악의 경우 시간 복잡도가 지수적으로 증가할 수 있습니다. 

 

# DFS의 기능

그렇다면 "해당분기를 완벽하게 탐색한다"라는 행위로 우리는 어떤것을 얻을 수 있을까?

1.  시작점에서 도착점까지의 경로를 찾기 위해
2. 컴파일러는 각 심볼의 유효 범위를 판단
3. 네트워크의 구성요소를 찾거나, 최단 경로를 찾는 등의 문제를 해결할 때 
4. 게임의 AI는 DFS 알고리즘을 사용하여, 다음에 어떤 수를 둘지를 결정
5. 소프트웨어의 모든 경로를 탐색하여 오류를 찾을 수 있습니다.

 

# BFS vs DFS

어느 알고리즘이 더 효율적인지 판단하기 위해서는 그래프의 특성과 탐색 목적에 따라 달라집니다.

BFS 알고리즘은 그래프의 구조가 깊고 넓이가 좁은 경우에 효율적입니다.

반면에 DFS 알고리즘은 그래프의 구조가 깊고 넓이가 넓은 경우에 효율적입니다.

그러나 일반적으로 BFS 알고리즘이 DFS 알고리즘보다 더 효율적인 경우가 많습니다. 그 이유는 BFS 알고리즘이 최단 경로를 보장하며, 그래프의 깊이가 어느 정도 깊어졌을 때 DFS 알고리즘은 스택 오버플로우(너무 많은 재귀함수 생성) 등의 문제가 발생할 수 있기 때문입니다.

 

 

 

 

# Reference

ChatGPT