그래프 (BFS, DFS, 인접리스트)
트리는 그래프의 특수한 형태(사이클 없음 + 단일 부모)였다면, 그래프는 그 제약을 모두 풀어 노드들이 임의의 방식으로 연결될 수 있는 가장 일반적인 자료구조이다. 도로망·SNS 인맥·웹 페이지의 하이퍼링크·전력망·항공 노선·통신 토폴로지·게임 맵까지, 현실 세계의 거의 모든 네트워크가 그래프로 모델링된다. 그래프 위에서 동작하는 탐색 알고리즘 BFS·DFS는 이후 등장하는 거의 모든 그래프 알고리즘(최단 경로·최소 신장 트리·위상 정렬 등)의 토대가 되며, 그 위에서 다익스트라·크루스칼·프림 같은 고급 알고리즘이 얹어진다. 본 글은 그래프의 정의·표현 방법·탐색 알고리즘을 세심하게 정리한다(출처: 위키백과 — Graph (abstract data type)). 제가 학교 알고리즘 수업에서 BFS와 DFS의 차이를 처음 손으로 그려 본 후로는 "큐는 옆으로 퍼지고 스택은 깊이 파고든다"는 한 줄로 두 알고리즘의 동작이 완전히 정리되었다.
그래프의 정의와 분류 — 방향·가중치·연결성
그래프(Graph) G는 정점(Vertex, 노드)의 집합 V와 간선(Edge, 노드 간 연결)의 집합 E의 쌍 G = (V, E)로 정의된다. 이 단순한 정의 안에 표현 가능한 구조의 폭은 사실상 무제한이며, 그래프의 종류를 분류하는 기준만으로도 시험 답안에서 자주 묻는 항목이 된다.
| 분류 기준 | 종류 | 특징 |
|---|---|---|
| 간선 방향 | 무방향 그래프 / 방향 그래프 | 방향 그래프는 u→v와 v→u가 다름 |
| 가중치 유무 | 가중 그래프 / 비가중 그래프 | 가중 그래프는 간선마다 비용·거리 |
| 연결성 | 연결 그래프 / 비연결 그래프 | 모든 노드가 하나의 컴포넌트에 속하는가 |
| 사이클 유무 | 순환 그래프 / 비순환 그래프 | DAG = 방향성 + 비순환 |
| 간선 밀도 | 희소 그래프 / 밀집 그래프 | E가 V²에 가까우면 밀집 |
| 가중치 부호 | 음 가중치 허용 / 비음 가중치 | 다익스트라는 음 가중치 불가 |
여기서 DAG(Directed Acyclic Graph)란 방향이 있되 사이클은 없는 그래프를 의미하며, 위상 정렬·작업 의존성·빌드 시스템·신경망 계산 그래프의 핵심 구조이다. 그래프 용어 중 시험에서 자주 묻는 항목으로 차수(degree)·진입 차수(in-degree)·진출 차수(out-degree)·경로(path)·사이클(cycle)·강한 연결 요소(strongly connected component) 등이 있는데, 각 용어를 한 줄씩 정확히 외워 두면 답안 작성이 훨씬 안정된다.
그래프의 표현 — 인접 행렬 vs 인접 리스트
그래프를 메모리에 표현하는 방법은 크게 두 가지로 정리된다. 인접 행렬(Adjacency Matrix)과 인접 리스트(Adjacency List)가 그것이며, 두 방식은 메모리·시간·구현 난이도에서 명확히 다른 트레이드오프를 가진다.
# 1) 인접 행렬 — V × V 크기의 2차원 배열
# M[i][j] = 1이면 i→j 간선이 존재
V = 4
M = [[0]*V for _ in range(V)]
edges = [(0, 1), (0, 2), (1, 3), (2, 3)]
for u, v in edges:
M[u][v] = M[v][u] = 1 # 무방향 그래프
# 2) 인접 리스트 — 각 노드마다 인접 노드의 리스트
adj = [[] for _ in range(V)]
for u, v in edges:
adj[u].append(v); adj[v].append(u)두 방식의 비교를 표로 정리하면 다음과 같다.
| 비교 항목 | 인접 행렬 | 인접 리스트 |
|---|---|---|
| 공간 복잡도 | O(V²) | O(V + E) |
| 두 노드 사이 간선 존재 확인 | O(1) | O(degree) |
| 한 노드의 모든 이웃 순회 | O(V) | O(degree) |
| 간선 추가·삭제 | O(1) | O(1) (앞쪽 삽입 시) |
| 적합한 그래프 | 밀집(dense) | 희소(sparse) |
| 실무 채택 | 작은 그래프·DP | 거의 모든 실전 알고리즘 |
여기서 희소 그래프(sparse graph)란 간선 수가 정점 수의 제곱에 한참 못 미치는 그래프(E ≪ V²)를 의미하며, 실세계 네트워크의 대부분이 이 부류에 속한다. SNS·도로망·웹은 노드 수에 비해 간선 수가 훨씬 적기 때문에, 인접 리스트가 메모리·시간 모두에서 압도적으로 효율적이다. 솔직히 제 경험상 학교 알고리즘 과제에서 처음 인접 행렬로 짰다가 V=10만짜리 그래프에서 메모리 부족이 나는 사고를 겪고 나서야 "큰 그래프는 무조건 인접 리스트"라는 원칙을 손끝으로 받아들였다.
그래프 탐색 알고리즘 — BFS와 DFS
그래프 탐색이란 한 시작 노드부터 도달 가능한 모든 노드를 정해진 순서로 방문하는 작업이다. 단순한 방문 자체가 의미 있는 일은 아니지만, 이 탐색 순서가 곧 최단 경로·연결 컴포넌트·사이클 검출 같은 거의 모든 그래프 알고리즘의 골격이 된다. 핵심 탐색 알고리즘 두 가지가 BFS와 DFS이다.
| 비교 항목 | BFS (너비 우선) | DFS (깊이 우선) |
|---|---|---|
| 자료구조 | 큐(Queue) | 스택(Stack) 또는 재귀 |
| 탐색 방향 | 시작점에서 가까운 노드부터 | 시작점에서 한 방향으로 끝까지 |
| 시간 복잡도 | O(V + E) | O(V + E) |
| 공간 복잡도 | O(V) | O(V) |
| 대표 응용 | 비가중 그래프 최단 경로, 레벨 탐색 | 사이클 검출, 위상 정렬, 백트래킹 |
# BFS — 큐 기반, 가장 가까운 노드부터
from collections import deque
def bfs(adj, start):
visited = [False] * len(adj)
order = []
q = deque([start])
visited[start] = True
while q:
u = q.popleft()
order.append(u)
for v in adj[u]:
if not visited[v]:
visited[v] = True
q.append(v)
return order
# DFS — 재귀 또는 스택
def dfs_recursive(adj, u, visited, order):
visited[u] = True
order.append(u)
for v in adj[u]:
if not visited[v]:
dfs_recursive(adj, v, visited, order)
def dfs_iterative(adj, start):
visited = [False] * len(adj)
order = []
stack = [start]
while stack:
u = stack.pop()
if visited[u]: continue
visited[u] = True
order.append(u)
for v in reversed(adj[u]): # 같은 순서 보장 위해 reverse
if not visited[v]:
stack.append(v)
return order두 알고리즘의 시간복잡도는 모두 O(V + E)로 동일하지만, 사용하는 자료구조와 방문 순서가 다르기 때문에 푸는 문제의 종류가 갈린다. BFS는 시작점에서 가까운 노드부터 차례로 방문하기 때문에 비가중 그래프의 최단 경로를 자연스럽게 구한다. 처음 도달한 시점의 깊이가 곧 최단 거리이며, 다익스트라가 아닌 단순 BFS 한 번이면 끝난다는 점이 결정적이다. DFS는 한 방향으로 끝까지 내려갔다가 되돌아오는 재귀적 특성을 가지므로 사이클 검출, 위상 정렬, 강한 연결 요소(SCC), 백트래킹 기반 탐색에 적합하다(출처: CLRS — Introduction to Algorithms).
솔직히 이건 예상 밖이었는데, 제가 학교 알고리즘 시험에서 같은 미로 문제를 BFS와 DFS로 풀어 본 후 BFS는 항상 최단 경로를 보장하지만 DFS는 그렇지 않다는 사실을 직접 확인하고 나서야 "탐색 자료구조의 선택이 알고리즘의 성격을 결정한다"는 점을 받아들였다. 다음 글에서는 이 탐색 알고리즘 위에 가중치를 얹어 만들어지는 정렬 알고리즘들을 이어 다룬다.
메타 디스크립션: 그래프 자료구조의 정의·분류·표현 방법(인접 행렬·인접 리스트)과 탐색 알고리즘 BFS·DFS의 차이를 코드 예시·비교표와 함께 자료구조 입문자 관점에서 세심하게 정리합니다.