그래프 탐색 (Graph Search)
그래프 탐색이란 정점 vertex와 간선 edge로 이루어진 그래프 네트워크에서 특정한 목적을 갖고 정점을 방문하는 것을 말한다. 다음은 주요한 그래프 탐색 알고리즘이다.
BFS (Breadth-First Search)
너비 우선탐색 BFS는 그래프에서 가까운 정점부터 먼 정점까지 차례로 탐색하는 알고리즘이다.
큐(Queue)를 이용해 구현할 수 있으며 동작과정은 다음과 같다.
1. 시작 정점(3)을 방문하고, 해당 정점을 큐에 넣는다.
2. 큐가 빌 때까지 다음을 반복:
- 큐에서 정점(3)을 꺼내 해당 정점과 연결된 모든 정점(5, 8, 25)을 큐에 넣고 방문한다.
- 큐에서 방문하지 않은 정점(5)을 꺼내 해당 정점과 연결된 모든 정점(1,2)을 큐에 넣고 방문한다.
- 큐에서 방문하지 않은 정점(8)을 꺼내 해당 정점과 연결된 모든 정점(none)을 큐에 넣고 방문한다.
BFS에서 큐를 사용하는 이유는 BFS의 특성 때문으로, 시작 정점으로부터 인접한 정점들을 순차적으로 탐색하기 때문에 선입선출(FIFO) 구조의 큐를 사용함으로써 먼저 들어온 정점부터 처리할 수 있다.
또한 방문할 정점을 큐에 넣기 전에 방문 여부를 체크해 중복 방문을 방지할 수 있다.
구현 코드
from collections import deque
def bfs(graph, start):
visited = [] # 방문여부 저장
queue = deque([start]) # 큐에 시작노드 추가
while queue:
node = queue.popleft()
if node not in visited: # 큐에서 꺼낸 노드가 방문하지 않은 노드라면
visited.append(node) # 방문리스트에 추가하고
queue += graph[node] # 해당 노드와 연결된 노드를 큐에 추가
return visited너비 우선 탐색 BFS의 시간 복잡도는 O(V+E) 로, 각 정점을 최대 한 번씩 방문하고 간선도 최대 한 번씩 검사하기 때문이다. 가까운 정점부터 먼 정점까지 차례로 탐색하므로 최단 경로를 찾는 데 유용한 알고리즘이다.
DFS (Depth-First Search)
깊이 우선탐색 DFS는 그래프나 트리 구조에서 시작 노드에서부터 시작하여 가능한 한 깊이 있는 경로를 탐색하고, 더 이상 진행할 수 없는 상황에 도달하면 역추적하여 다른 경로를 탐색하는 알고리즘이다.
일반적으로 1. 스택(Stack)이나 2. 재귀함수를 통해 구현할 수 있으며 동작과정은 다음과 같다.
1. 스택(Stack)
DFS에서는 한 정점에서 시작해 해당 분기를 완전히 탐색하기 때문에 후입선출(LIFO) 구조의 스택을 통해 깊이 우선탐색을 구현할 수 있다. 과정은 다음과 같다.
- 시작 노드를 스택에 넣는다.
- 스택이 빌 때까지 다음을 반복:
- 스택에서 노드를 하나 pop
- 해당 노드를 방문하지 않았다면 방문한다.
- 해당 노드의 인접 노드 중 방문하지 않은 노드를 스택에 넣는다.
구현코드
def dfs(graph, start):
visited = set() # 방문여부 저장
stack = [start] # 스택에 시작노드 추가
result = [] # 방문한 노드를 저장할 리스트
while stack:
node = stack.pop()
if node not in visited: # 스택에서 꺼낸 노드가 방문하지 않은 노드라면
visited.add(node) # 방문리스트에 추가
result.append(node) # 결과리스트에 추가
for neighbor in graph[node]: # 해당 노드의 인접 노드 중 방문하지 않은 노드 스택에 추가
if neighbor not in visited:
stack.append(neighbor)
return visited2. 재귀함수
- 시작 노드를 방문하고 방문 여부를 표시
- 모든 인접 노드에 대해 방문할 때까지 다음을 수행:
방문하지 않은 인접 노드가 있다면 해당 노드에 대해 재귀 호출
구현 코드
def dfs_recursive(graph, node, visited, result):
if node not in visited: # 현재 노드를 방문하지 않았다면
visited.add(node) # 방문 표시
result.append(node) # 결과 추가
for neighbor in graph[node]: # 현재 노드와 연결된 모든 인접 노드에 대해
dfs_recursive(graph, neighbor, visited, result) # 재귀 호출
return result깊이 우선탐색 DFS도 BFS와 바찬가지로 모든 정점을 한 번씩 방문하고, 각 간선도 최대 한 번씩 검사하기 때문에 시간 복잡도는 O(V+E) 이다. : 인접 리스트
인접 행렬 로 표현된 경우 각 정점에서 다른 정점으로의 연결 관계를 확인할 때 상수 시간 O(1)의 시간이 소요되어 모두 확인할 경우 O(V)만큼 소요되므로, O(V^2) 의 시간 복잡도를 갖는다.
BFS vs DFS
| BFS | DFS | |
|---|---|---|
| 탐색 방식 | 시작 정점으로부터 가까운 정점부터 순차적 탐색 | 한 정점에서 시작하여 분기별 완전 탐색 |
| 탐색 순서 | 가까운 정점부터 순차적 탐색 | 한 분기를 완전 탐색 후 다음 분기 |
| 자료구조 | 큐 (FIFO) | 스택 또는 재귀 함수 (LIFO) |
| 활용 | 최단 경로, 최소 신장 트리 등에 활용 | 위상 정렬, 강한 연결 요소 등에 활용 |
| 시간 복잡도 | O(V+E) | O(V+E) |
| 적용 예시 | 최단 경로를 찾을 때 | 그래프의 순회, 연결 요소 찾을 때 |
