[Algorithm] Depth/Breadth First Search

이번 포스팅에서는 깊이우선탐색(Depth First Search : DFS)과 너비우선탐색(Breadth First Search)에 대해서 알아보겠습니다. 두 알고리즘 모두 그래프에서 모든 노드를 방문하거나 특정 경로를 탐색하는 데 사용되며, 각각의 특성과 사용 방법에 차이가 있습니다.
 

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

DFS는 한 경로를 끝까지 탐색한 후에 다른 경로로 이동하는 방식입니다. 주로 재귀(Recursion)나 스택(Stack)을 사용해 구현합니다.

 

1. 알고리즘 요약

1) 시작 node에서 출발합니다.
2) 방문한 node를 기록하고, 해당 node의 인접 node 중 방문하지 않은 node로 이동합니다.
3) 더 이상 이동할 node가 없으면 이전 단계로 백트래킹(Backtracking)합니다.
4) 모든 node를 방문할 때까지 반복합니다.
 

2. Python 코드 예시

def dfs_rc(graph, start_node, visited=None):
    if visited is None:
        visited = set()
    
    # 방문 처리
    visited.add(start_node)
    print(start_node, end=' ')

    # 인접 노드 탐색
    for neighbor in graph[start_node]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

 

BFS (Breadth First Search, 너비 우선 탐색)

BFS는 현재 노드와 인접한 모든 노드를 먼저 탐색한 후, 그다음 깊이로 이동하는 방식입니다. 주로 큐(Queue)를 사용하여 구현합니다.

 

1. 알고리즘 요약

1) 시작 node를 queue에 넣고 방문 표시합니다.
2) queue에서 node를 꺼내 인접한 모든 node를 queue에 추가합니다.
3) 더 이상 queue가 비어있지 않을 때까지 반복합니다.
 

2. Python 코드 예시

from collections import deque

def bfs(graph, start_node):
    visited = set()
    queue = deque([start_node])
    
    while queue:
        node = queue.popleft()  # 큐에서 노드 추출
        if node not in visited:
            print(node, end=' ')
            visited.add(node)
            
            # 인접 노드를 큐에 삽입
            queue.extend(graph[node])

 
 

DFS vs. BFS 비교

	DFS	BFS
장점	현재경로의 node를 기억하기 때문에 상대적으로 적은 메모리 사용 찾으려는 node가 깊은 곳에 있는 경우 BFS 보다 빠르게 탐색	답이 되는 경로가 여러 개인 경우에도 최단경로임을 보장 최단경로가 존재하면 그 깊이가 아무리 깊어도 답을 찾을 수 있음
단점	해가 없는 경로를 탐색할 때 가장 마지막 depth까지 탐색 후 다음 경로로 넘어감(효율성을 위해 일정 깊이로 탐색을 제한하는 방법 사용) DFS를 통해 획득한 해가 최적이라 확신할 수 없음	중간 Save를 해야하기 때문에 공간복잡도*가 높다

 
* : 두 알고리즘의 시간 복잡도는 동일
 

When to Use?

1) 그래프의 모든 정점을 방문하는 것이 주요 과제 : DFS/BFS 둘 다 적용가능
2) 경로의 특징을 저장해야 하는 과제 : DFS유용
3) 최적의 거리를 구해야하는 과제 : BFS유용
 
 
 
referenece)
https://www.codecademy.com/article/tree-traversal

Tree Traversal: Breadth-First Search vs Depth-First Search | Codecademy