[DFS/BFS] DFS/BFS (1) 개요

DFS

• 깊이 우선 탐색 알고리즘
• 특정한 경로로 탐색하다가 특정한 상황에서 최대한 깊숙이 들어가서 노드를 방문한 후, 다시 돌아가 다른 경로로 탐색하는 알고리즘
• 스택 자료구조 이용
  • 스택을 쓰지 않아도 되며, 탐색 수행 시 데이터 개수가 N개라면 O(N) 시간 소요
  • 재귀함수를 이용했을 때 매우 간결하게 구현 가능
• 동작 과정
  1. 탐색 시작 노드를 스택에 삽입하고 방문 처리
  2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리. 방문하지 않은 노드가 없으면 스택에서 최상단 노드를 꺼냄.
  3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복
• 예시

• 인접한 노드 중 방문하지 않은 노드가 여러 개 있으면 일반적으로 번호가 낮은 순서부터 처리
• 소스코드

# DFS 메서드 정의
def dfs(graph, v, visited):
  # 현재 노드 방문 처리
  visited[v] = True
  print(v, end = ' ')
  # 현재 노드와 연결된 다른 노드를 재귀적으로 방문
  for i in graph[v]:
    if not visited[i]:
      dfs(graph, i, visited)

# 각 노드가 연결된 정보를 리스트 자료형으로 표현 (2차원 리스트)
graph = [
  [],
  [2, 3],
  [1, 4, 5],
  [1, 6, 7],
  [2],
  [2],
  [3],
  [3, 8, 9],
  [7],
  [7]
]

# 각 노드가 방문된 정보를 리스트 자료형으로 표현 (1차원 리스트)
visited = [False] * 10

# 정의된 DFS 함수 호출
dfs(graph, 1, visited)

# 실행결과: 1 2 4 5 3 6 7 8 9

BFS

• 너비 우선 탐색
• 가까운 노드부터 탐색
• 큐 자료구조 이용
  • 인접한 노드를 반복적으로 큐에 넣도록 알고리즘을 작성하면 먼저 들어온 것이 먼저 나가게 되어, 가까운 노드부터 탐색 진행 가능
  • 파이썬에서는 collections 모듈의 deque 라이브러리 이용
  • 탐색 수행에 O(N) 시간 소요
  • 실제 수행 시간은 BFS가 DFS보다 조금 더 빠르게 동작
• 동작 과정
  1. 탐색 시작 노드를 큐에 삽입하고 방문 처리
  2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리
  3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복
• 예시

• 소스코드

from collections import deque

# BFS 메서드 정의
def bfs(graph, start, visited):
  # 큐 구현을 위해 deque 라이브러리 사용
  queue = deque([start])
  # 현재 노드를 방문 처리
  visited[start] = True
  # 큐가 빌 때까지 반복
  while queue:
    # 큐에서 하나의 원소를 뽑아 출력
    v = queue.popleft()
    print(v, end = ' ')
    # 해당 원소와 연결된, 아직 방문하지 않은 원소들을 큐에 삽입
    for i in graph[v]:
      if not visited[i]:
        queue.append(i)
        visited[i] = True

# 각 노드가 연결된 정보를 리스트 자료형으로 표현 (2차원 리스트)
graph = [
  [],
  [2, 3],
  [1, 4, 5],
  [1, 6, 7],
  [2],
  [2],
  [3],
  [3, 8, 9],
  [7],
  [7]
]

# 각 노드가 방문된 정보를 리스트 자료형으로 표현 (1차원 리스트)
visited = [False] * 10

# 정의된 bfs 함수 호출
bfs(graph, 1, visited)

# 실행결과: 1 2 3 4 5 6 7 8 9

DFS vs BFS

	DFS	BFS
동작 원리	스택	큐
구현 방법	재귀 함수 이용	큐 자료구조 이용