그래프 탐색 알고리즘은
주어진 그래프에서 원하는 방식으로 정점들을 방문해 나가는 절차를 말한다.
가장 널리 쓰이는 탐색 방식은 깊이 우선 탐색(DFS) 과 너비 우선 탐색(BFS) 이 두 가지이다.
DFS(깊이우선탐색)
DFS는 이름 그대로 가장 깊은 곳까지 먼저 파고드는 탐색 방식이다.
동작 개념
- 시작 정점에서 탐색을 시작한다.
- 현재 위치에서 갈 수 있는 인접 정점 중 하나를 선택해 이동한다.
(보통 인접 정점 리스트가 정렬되어 있지 않다면, 저장된 순서대로 탐색) - 더 이상 방문할 수 있는 정점이 없으면 이전 정점으로 되돌아감.
- 방문되지 않은 정점이 남아 있다면 그 정점에서 다시 탐색을 반복한다.
특징
스택 구조로 구현 가능하며, 재귀 함수를 쓰면 자연스럽게 시스템 스택이 활용된다.
- 인접 리스트 기반 DFS 시간복잡도: O(V + E)(정점 + 간선)
구현 (Py)
# 그래프를 인접 리스트(Adjacency List) 형태로 표현
# 각 노드는 key, 해당 노드와 연결된 인접 노드들은 리스트로 관리
graph = {
1: [2, 3], # 1번 노드는 2번, 3번과 연결됨
2: [4], # 2번 노드는 4번과 연결됨
3: [2, 5], # 3번 노드는 2번, 5번과 연결됨
4: [], # 4번 노드는 연결된 노드 없음
5: [] # 5번 노드도 연결된 노드 없음
}
# 방문한 노드를 기록하는 집합(Set)
# 중복 방문을 방지하며, 탐색 여부를 매우 빠르게 확인 가능 (O(1))
visited = set()
# 깊이 우선 탐색(DFS, Depth-First Search) 구현 함수
def dfs(node):
visited.add(node) # 현재 노드를 방문 처리
print(node, end=' ') # 방문한 노드를 출력
# 현재 노드에 인접한 노드들 순회
for nxt in graph[node]:
# 만약 방문하지 않은 노드라면
if nxt not in visited:
dfs(nxt) # 해당 노드로 재귀적으로 DFS 호출(더 깊이 탐색)
print("DFS 탐색 순서:") # 출력 제목
dfs(1) # DFS를 1번 노드에서 시작
print() # 줄바꿈
BFS(너비우선탐색)
BFS는 DFS와 반대로 가까운 정점부터 순서대로 탐색하는 방식이다.
동작 개념
- 시작 정점을 큐에 넣고 방문 처리한다.
- 큐의 맨 앞에서 정점을 꺼낸다.
- 그 정점과 인접한 정점들 중 아직 방문하지 않은 정점들을 큐에 추가
- 큐가 빌 때까지 2~3 반복
특징
먼저 들어온 노드를 먼저 꺼내는 FIFO 구조의 큐 사용를 사용하며 “레벨 단위”로 탐색하기 때문에
시작 정점으로부터의 최단 거리를 자연스럽게 구할 수 있음
- 인접 리스트 기반 DFS 시간복잡도: O(V + E)(정점 + 간선)
구현 (Py)
from collections import deque # BFS에서 사용할 큐(queue) 자료구조 import
# 그래프를 인접 리스트(Adjacency List) 형태로 구성
graph = {
1: [2, 3], # 1번 노드는 2, 3과 연결
2: [4], # 2번 노드는 4와 연결
3: [2, 5], # 3번 노드는 2, 5와 연결
4: [], # 4번은 인접 노드 없음
5: [] # 5번도 인접 노드 없음
}
# BFS(너비 우선 탐색) 함수 정의
def bfs(start):
q = deque([start]) # 큐 생성 및 시작 노드를 큐에 넣기
visited = {start} # 방문한 노드를 기록하는 집합(Set), 시작 노드를 방문 처리
print("BFS 탐색 순서:", end=' ') # 출력 라벨
# 큐가 빌 때까지 반복 (탐색 종료 조건)
while q:
now = q.popleft() # 큐의 가장 앞(front)에서 노드를 꺼냄
print(now, end=' ') # 현재 방문한 노드 출력
# 현재 노드(now)에 연결된 인접 노드들을 확인
for nxt in graph[now]:
# 아직 방문하지 않은 노드라면
if nxt not in visited:
visited.add(nxt) # 방문 표시
q.append(nxt) # 큐에 넣어서 다음 레벨 탐색 준비
# 1번 노드에서 BFS 시작
bfs(1)
print() # 줄바꿈
DFS vs BFS
| 탐색 방향 | 깊게 들어감 | 넓게 퍼짐 |
| 자료구조 | 스택 or 재귀 | 큐 |
| 쓰임새 | 백트래킹, 순열/조합 탐색 | 최단 거리 탐색 |
| 시간복잡도 | O(V+E) | O(V+E) |