☀️ haejun

Today-·Total-

DFS와 BFS 그래프 탐색

4 min read

Summary

  • DFS는 시작 노드에서 자식 노드를 깊이 우선으로 탐색하며, 주로 스택이나 재귀 함수로 구현한다.
  • DFS는 메모리 효율이 좋고 순환 감지에 유리하지만 최단 경로 탐색에는 적합하지 않고 무한 루프 위험이 있다.
  • BFS는 인접한 노드들을 먼저 탐색하는 너비 우선 방식으로, 큐(선입선출)를 활용해 구현한다.
  • BFS는 가중치가 없는 그래프에서 최단 경로를 찾는 데 탁월하지만, 노드 수가 많거나 분기 계수가 클수록 메모리 소모가 크다.
  • 모든 노드를 방문하거나 깊은 탐색이 필요하면 DFS를, 최단 거리를 구해야 한다면 BFS를 선택한다.

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

개념

DFS는 시작 노드에서 자식 노드들을 깊이를 우선으로 순서대로 탐색하는 알고리즘이다. Stack을 활용한 반복문에 쓰이거나, 재귀문을 통해 구현된다.

탐색과정

  1. 특정 노드를 방문했으면, 방문했다고 표시
  2. 해당 노드의 자식 노드를 탐색
  3. 더이상 자식 노드가 없으면 역추적
  4. 방문한 적이 없는 노드를 탐색
  5. 모든 노드를 방문할 때까지 위 프로세스 반복

특징

구분내용
장점메모리 효율적, 순환 감지 가능
단점최단 경로 탐색 부적합, 무한 루프 위험

구현 방법

graph = {1: [2,3,4], 2: [5], 3: [5], 4: [], 5: [6,7], 6: [], 7: [3]}

반복 구현(Stack)

def stack_dfs(root):
    visited = []
    stack = [root]
    while stack:
        v = stack.pop()
        if v not in visited:
            visited.append(v)
            for w in graph[v]:
                stack.append(w)
    return visited
 
print(stack_dfs(1))  # [1,4,3,5,7,6,2]

재귀 구현

def recursive_dfs(root, visited=[]):
    visited.append(root)
    for w in graph[root]:
        if w not in visited:
            visited = recursive_dfs(w, visited)
    return visited
 
print(recursive_dfs(1, []))

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

개념

BFS는 시작 노드에서 자식 노드들을 너비를 우선으로 순서대로 탐색하는 알고리즘이다. 가중치가 없는 그래프에서 최단거리를 구하는 문제에 활용되며, Queue를 활용해 다음 방문할 노드를 추적한다.

탐색 과정

  1. 시작 노드를 Queue에 삽입
  2. Queue에서 노드를 제거하고 검사
  3. 목표 노드라면 검색 완료
  4. 방문하지 않은 자식 노드를 Queue에 삽입
  5. Queue가 비워질 때까지 반복

특징

구분내용
장점최단 경로 탐색에 탁월
단점메모리 소모가 크고 노드 수가 많으면 비효율적

구현 방법

from collections import deque
 
def BFS(root):
    visited = [root]
    queue = deque([root])
    while queue:
        v = queue.popleft()
        for w in graph[v]:
            if w not in visited:
                visited.append(w)
                queue.append(w)
    return visited
 
print(BFS(1))  # [1,2,3,4,5,6,7]

Reference

Graph View